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
