600. Excavations
Brief description:
。。。一个古城遗迹 n 个建筑。。我们知道这些建筑的类型和掩埋的深度。type。depth。
。。。你有一个最大可以挖 D 米的挖掘机。。你不知道 D 。。但是你知道你恰好挖了 K 次。。
。。并且挖上来的建筑种类恰好有哪些 。。found。。。。。
。。问哪些挖掘方案（K-tuples）是有可能的。。
Analysis:
。。。题目很绕。。先明确点东西。。
。首先。。对于任意一个方案。。都至少要覆盖所有 found 。。然后对于那些未出现在 found 里的元素。。
他们的 depth 至少要 ＞ 所有 found 里出现的最小值。否则会有不该发现的被发现。。。。
。。。总之出现在 found 里和没出现在 found 里的两类建筑。。是要分开考虑的。。。
。。 然后似乎不可避免的要枚举 D。。。当然其实是枚举那个被挖出来的最深元素。（离散化 + 避免重复计数）。。。
。深度确定以后。。又把所有的元素分为了两类。。设当前枚举的深度为 d。。那么对于所有大于 d 的元素。。
。。。他出现不出现在 found 里其实无关紧要了。。反正看不见。。。
。。。那么我们再枚举大于 d 的元素在 tuple 里的个数 i。。这一部分的计数只需要组合数即可。。。
。。子问题是在这些小于 d 的元素中选取 k-1-i 个。。保证每类至少选一个的方案数。。。
等等。。这样。。还得特判那个被挖出去元素恰好是哪个种类。。重来。。
。我们枚举最小的出现在 tuple 里的但是没有被发现的不在 found 中的那个元素（有可能不存在）。。。
。。子问题是在所有小于 d 且出现在 found 的元素中。。选取 k 个，使得每一类至少有一个。。。
。。 子问题的 DP。。每阶段枚举。选了几个 和 其中最小的是谁 即可。
const int N = 60;
LL Binom[N][N], dp[N][N];
VI A[N]; int LIM, n, m;
LL f(int n, int k){
if (n > k) return 0;
if (!n--) return k ? 0 : 1;
LL &res = dp[n][k];
if (!~res){
res = 0; REP_1(i, min(k, SZ(A[n]))) REP(j, SZ(A[n])-i+1){
if (A[n][j] >= LIM) break;
res += Binom[SZ(A[n])-j-1][i-1] * f(n, k-i);
}
}
return res;
}
class Excavations {
public:
long long count(vector <int> kind, vector <int> depth, vector <int> found, int K) {
REP(i, N){Binom[i][0] = 1; REP_1(j, i) Binom[i][j] = Binom[i-1][j-1] + Binom[i-1][j];}
n = SZ(kind), m = SZ(found); REP(i, m+1) CLR(A[i]);
REP(i, n) A[find(ALL(found), kind[i]) - found.begin()].PB(depth[i]);
REP(i, m+1) SRT(A[i]);
FLC(dp, -1); LIM = INF; LL res = f(m, K);
DWN(i, SZ(A[m]), 0){
FLC(dp, -1), LIM = A[m][i];
REP_1(k, K-m) res += Binom[SZ(A[m])-i-1][k-1] * f(m, K-k);
}
return res;
}
};
900. FoxTheLinguist
Brief description:
。。。有 m 种语言，开始都是 0 级。。有一些课程。。课程是形如。。。(Ai, Bj, w) 的形式。。（如果 A 语言够 i 级。。那么支付 w 费用。。可以令 B 语言到达 j 级。。。
。。问所有语言都到达 9 级。。至少需要多少花费。。
Analysis:
。。注意到是树形图就行了。。
。。建模是。。每个语言拆成 [0, 9] 十个点。。 。。添加一个根结点。。连到所有语言的 0 级。。代价为 0。。
。。。。然后对每个语言的除了 0 以外的等级。。都向低一级连一条代价为 0 的边。。。。
。。（。如果边的形式是从一个语言集合到另一个语言还能做么。。
External link:
https://apps.topcoder.com/wiki/display/tc/SRM+584
https://gist.github.com/lychees/6202038
