某岛

… : "…アッカリ~ン . .. . " .. .
May 27, 2014

SRM 619

600. GoodCompanyDivOne

Brief description:

某公司的人员从属关系是一颗有根树,有 N 个技能,每个技能的学习费用是 w[i],每个结点和其所有孩子组成一个部门(department),要求每个部门的所有人员所从事的工作不同,每个人需要学习恰好两个技能,只有在学习了技能 i 的情况下才可以从事工作 i,注意 department 之间是相互独立的,一个人可以在不同的 department 中从事不同的工作。

Analysis:

Tree DP + KM。。。
算法显然。。。

对于结点 u 为根的 department。。设 dp[u][x] 表示该结点从事工作 x 时,整个以 u 为根的子树的最少代价。。。
。通过对子树的递归得到每个孩子从事各个工作时的代价。。
。 。再枚举 u 所从事的工作。。则可以通过匹配计算最优解。。。

这里主要来解决当时我的一个遗留问题。。。
。。。。对于 u 此时所从事的工作。这个技能是必须学习的。。除此之外还需要枚举另一个技能来更新与该技能相关的 dp 值。。
。。通过枚举这个。。将更新另一个 dp 值。。。

。。。现场生的时候我一度认为。。。只需要枚举每个结点从事的工作 x。。。这个附带的技能取 x 之外 cheapest 的那个就可以了。。
。。提交前又把这个改回来了。。(反正两者复杂度一样。。。)

。。不过后来又还原回去交了一下。。。也是对的。。。现在我来试图证明这个结论。。。。
【数学归纳】【替换链】【无穷递降】

归纳证明。。。trivial 情况显然。。

。。。。考虑 r 结点的某个孩子 u。。。假设取 (w_x, w_y) 时比 (c_x, w_x) 时更优。。。(这里 c_x 是除 w_x 之外 cheapest 的那个。。)
那么因为 c_x   <  w_y。。。则一定 u 的某个孩子 v 在这种情况下更优。。

而这只能是因为其选到了。。dp[v] [x]。。。

也就是                        没有                                   优。
(c_x , w_x)                                (w_x, w_y)
       |                                                    |
dp[v][bad]                                     dp[v][x]


因为 w_y 的空缺。。。bad 最坏情况至少 = y。。。

此时 v 结点的代价是。。
(c_y, w_y)       (c_x, w_x)

。。因为 c_y <= w_x 。。不能保证此时 u 结点取 (w_x, w_y) 更优。。。
。。因此继续看 v 结点的孩子 w。。。

也就是要求。。。
dp[w][x]  < dp[w][y]

。。。。。。。。。

。。。反复这个过程。。这条 “替换链” 将会产生。。。

(c_x, w_x)   (w_x, w_y)
(c_y, w_y)   (c_x, w_x)
(c_y, w_x)   (c_y, w_y)
(c_y, w_y)   (c_x, w_x)
(c_y, w_x)   (c_y, w_y)
...           
这样的循环。。。
。。。而在任何一层都不会出现 (w_x, w_y)  更优。。。因此命题得证。
const int N = 31, M = 31;
int n, m;

namespace KM{ // KM-最优匹配
    typedef int weight_t;
    const weight_t weight_MAX = INF;
    const weight_t weight_MIN = -INF;

    weight_t W[N][N], lx[N], ly[M], slack[M];
    int px[N], py[M]; bool vx[N], vy[M];
    int n;

#define w(x, y) (lx[x] + ly[y] - W[x][y])

    bool dfs(int x){
        vx[x] = 1; REP(y, m) if (!vy[y]){
            if (!w(x, y)){ //!
                vy[y] = 1; if (py[y] == -1 || dfs(py[y])){
                    py[y] = x, px[x] = y;
                    return 1;
                }
            }
            else {
                checkMin(slack[y], w(x, y));
            }
        }
        return 0;
    }

    weight_t run(){
        if (n > m) return INF;
        FLC(px, py, -1), fill(lx, lx + n, weight_MIN), fill(ly, ly + m, 0);
        REP_2(x, y, n, m) checkMax(lx[x], W[x][y]);

        REP(x, n){
            fill(slack, slack + m, weight_MAX); while (1){
                fill(vx, vx + n, 0), fill(vy, vy + m, 0);
                if (dfs(x)) break; weight_t d = weight_MAX;
                REP(i, m)  if (!vy[i]) checkMin(d, slack[i]);
                REP(i, n) if (vx[i]) lx[i] -= d;
                REP(i, m) if (vy[i]) ly[i] += d; else slack[i] -= d;
            }
        }
        weight_t res = 0; REP(x, n){
            if (W[x][px[x]] == -INF) return INF;
            res += W[x][px[x]];
        }
        return -res;
    }

#undef w

//Interface.. . //{
    void add_node(int t[]){
        REP(i, m) W[n][i] = -t[i]; ++n;
    }

    void init(){
        n = 0;
    }
} //using namespace KM;

int dp[N][N], w[N]; vector<int> adj[N];

#define v (*it)
void dfs(int u = 0){
    ECH(it, adj[u]) dfs(v);
    REP(i, m) dp[u][i] = INF;
    REP(i, m){
        KM::init(); ECH(it, adj[u]){
            int t = dp[v][i]; dp[v][i] = INF;
            KM::add_node(dp[v]); dp[v][i] = t;
        }
        int t = KM::run();
        dp[u][i] = w[i] + t;
    }
}

class GoodCompanyDivOne {
public:
	int minimumCost(vector <int> superior, vector <int> training) {
		n = SZ(superior); REP(i, n) adj[i].clear(); FOR(i, 1, n) adj[superior[i]].PB(i);
		m = SZ(training); SRT(training); w[0] = training[0] + training[1]; FOR(i, 1, m) w[i] = training[0] + training[i];
        FLC(dp, -1); dfs(); int z = INF; REP(i, m) checkMin(z, dp[0][i]); if(z==INF) z = -1;
		return z;
	}
};

1000. SimilarSequencesAnother

Brief description:

A 串与 B 串 k-相似的条件是分别从两个串中删除至多 k 个元素之后得到的串相等。
。。现给定 A,B 串的长度 n 和字符集的大小 m 。。问有多少对串 2-相似。。。

Analysis:

这个题实在是十分 Nice .。。。考验对状态的反复提炼。。。

先弱化。。
考虑 A 串 B 串已经给定。。判断是否可行。。。
那么我们有 dp[N][N][3][3]。。最后 [3][3] 表示删除的次数。。。对于固定的一个串。。他最后 dp[N][N][3][3] 的结果是固定的。。。
。。。我们把那些合法方案相同的串用同一个状态表示。。。状态压缩。。。。也就是 s = 1<<9 。。。。


回到原问题。。。
....设计一个模糊的状态。。(i, j, s) 表示。。。
当前 A 串考虑到第 i 个位置, B 串考虑到 j 个位置。。当前合法状态集合是 s。。的方案数。。
。。。

。。。这样考虑后 j 维记录的东西过多。。。实际我们只需要记录。。。
————————
...                   a[i] 
... b[i-2] b[i-1] b[i] b[i+1] b[i+2] 

。。。与 a[i] 相邻的 5 个 b 的位置的数就够了。(只需要保存前四个。b[i+2] 转移的时候枚举。。。

。。进一步。。。我们并不关心她们具体是多少。。。而只需要知道它们之间的相对大小关系。
。。。(。。错了,没有相对大小关系。。。而只有是否相等的关系。!!。。)。




例如
3 3 2 5 4...
我们可以精简成
0 0 1 2 3 ...


。。。也就是用 最小表示法 压缩这则状态。。。把 m 的限制去掉。。。。

这样总的状态 (i, b, s)。。。
只有 。。N * 4^4 * 2^9 种。。。(实际上中间那一维经过最小表示法之后。。远达不到 4^4 的上界。。)
。。。转移需要分别枚举 b[i+2] 和 a[i]。。。复杂度 O(5^2)。。。两个转移因子分别记做 c1 和 c2。。。。
并根据是否和之前状态中的某个数相同进行讨论即可。。c = b==up ? m-up : 1。。。
累加。。if (ss) v += u*c1*c2;

注意如果 ss 为 0 那么说明不存在任意一个合法状态。。。直接跳过即可。。。我居然因为这个原因 SB 调试好久。。
//}/* .................................................................................................................................. */

const int N = 109, M = 9;
map<PII, Int> dp[2]; int _b[5], b[5], p, q;

void decode(int x){
    REP(i, 4) b[i] = x%4, x/=4;
}

int encode(){
    int x = 0; DWN(i, 4, 0) x*=4,x+=b[i];
    return x;
}

void recode(){
    MII H; int n = 0; FOR(i, 1, 5){
        if (!CTN(H, _b[i])) H[_b[i]] = n++;
        b[i-1] = H[_b[i]];
    }
}

class SimilarSequencesAnother {
public:

    int getCount(int n, int m){

        p = 0, q = 1; RST(b); CLR(dp[p]); dp[p][MP(1, encode())] = m;
        b[3] = 1; dp[p][MP(1, encode())] = Int(m)*(m-1);

#define u (it->se)
#define v dp[p][MP(ss, encode())]

        DO(n){
            swap(p, q); CLR(dp[p]); ECH(it, dp[q]) if (u){
                int s = it->fi.fi; decode(it->fi.se); CPY(_b, b); int up1 = *max_element(b, b+4)+1; FOR_1_C_N(_b[4], 0, up1){
                    Int c1 = _b[4] == up1 ? m-up1 : 1; recode();
                    int up2 = max(_b[4]+1, up1); FOR_1(a, 0, up2){
                        Int c2 = a == up2 ? m-up2 : 1; int ss = 0; REP(i, 9) if (_1(s, i)){
                            int x = i%3, y = i/3; REP(dx, 2) REP(dy, 3){
                                int xx = x+dx, yy = y+dy; if (xx > 2 || yy > 2) continue;
                                if (dx || a == _b[2-xx+yy]) ss |= _1(yy*3+xx);
                            }
                        }
                        if (ss) v += u*c1*c2;
                    }
                }
            }
        }

        Int res = 0; ECH(it, dp[p]){
            decode(it->fi.se); if (!b[2] && !b[3]) res += u;
        }

        return res;
    }
};

External link:

https://apps.topcoder.com/wiki/display/tc/SRM+619
https://gist.github.com/lychees/028faa9c2b009fb7f297