某島

… : "…アッカリ~ン . .. . " .. .
August 11, 2013

SRM 584

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