Brief description:

Problem 250. KingdomAndTrees
给定一个数列，要求修复成递增序列。。（所有项都是正数。。。
。定义修复代价为变动最大的数字改变了多少。。求最小修复代价。。。

Problem 450. KingdomAndDice
给定两块骰子。。数字选自 {1, x} 。。
其中一块骰子上的数字已经全部确定。。另一块骰子部分确定。。
。。先要求确定剩下的数字。。使得该游戏尽可能公平。

Problem 1000. KingdomAndCities
计数：求 n 个顶点、m 条边、其中前 k 个顶点恰好连 2 条边时形成连通图的方案数。
( n, m <= 50, k <= 2 .. .

Analysis:

Problem 250. KingdomAndTrees
。。。枚举 i, j 对每对 i, j 更新一下上界。
。（如果出现 Ai <= 1 则锁定其为 1 。。重新更新上界。。。 。（好像也可以二分答案贪心。。 Problem 450. KingdomAndDice 。。。略） 裸 O(n5) 多重背包。。。 dp[i][j] 表示当前使用了 i 个物品，能否得到和等于 j 的方案。 Problem 1000. KingdomAndCities 。。。( 移步。。。

class KingdomAndTrees {
public:
	int minLevel(vector <int> A) {

		int n = SZ(A), res = 0;

		REP(i, n) FOR(j, i+1, n){
		    int t = (j - i + A[i] - A[j] + 1) / 2;
		    if (A[i] - t > 0) checkMax(res, t);
		    else checkMax(res, j - i - A[j] + 1);
		}

		return res;
	}
};

.. .
const int N = 59, M = N * N;

bool dp[N][M]; int cnt[N];
int n, m, s, nn, b;

class KingdomAndDice {
public:
	double newFairness(vector <int> A, vector <int> B, int X) {

	    n = SZ(A); s = n * n; m = s / 2, nn = 0, b = 0;

	    SRT(B), RST(cnt);
	    DWN(i, n, 0) if (A[i] == 0){
            ++nn;
	    }
	    else {
	        int t = lower_bound(ALL(B), A[i]) - B.begin();
            --cnt[t], b += t;
	    }

        cnt[0] = nn; REP(i, n){
            if (i == n - 1) cnt[i+1] = min(nn, cnt[i+1] + max(0, X - B[i]));
            else cnt[i+1] = min(nn, cnt[i+1] + max(0, B[i+1] - B[i] - 1));
        }

        RST(dp), dp[0][b] = true;

        REP(ii, n+1) REP(j, cnt[ii]){
            DWN(i, nn, 0) DWN_1(j, s-ii, b){
                if (dp[i][j]) dp[i+1][j + ii] = true;
            }
        }


        if (dp[nn][m]) return (DB) m / s;

        if (!(s&1)){
            REP(i, M){
                if (m-i>=0 && dp[nn][m-i]) return (DB) (m - i) / s;
                if (m+i<=s && dp[nn][m+i]) return (DB) (m + i) / s;
            }
        }
        else {
            REP(i, M){
                if (m+i<=s && dp[nn][m+i]) return (DB) (m + i) / s;
                if (m-i>=0 && dp[nn][m-i]) return (DB) (m - i) / s;
            }
        }
	}
};

.. .
const int N = 59;

int C[N*(N-1)/2+1][N], S[N][N], A[N][N];
int n, m, k;


int f0(int n, int m){
    return A[n][m];
}

int f1(int n, int m){
    int res = 0; --n, m -= 2;
    FOR(i, 1, n) FOR_1(j, 0, m)
        INC(res, pdt(i, n-i, C[n][i], f0(n-i, m-j), f0(i, j)));
    DIV(res, 2); INC(res, pdt(C[n][2], f0(n, m)));
    return res;
}

int f1_(int n, int m){
    int res = 0; --n, m -= 2;
    FOR(i, 1, n) FOR_1(j, 0, m)
        INC(res, pdt(i, n-i, C[n][i], f0(n-i, m-j), f0(i, j)));
    INC(res, pdt(sqr_M(C[n][1]), f0(n, m)));
    return res;
}

int f2(int n, int m){

    int res = f1_(n-1, m-1); n -= 2, m -= 4;
    INC(res, pdt(sqr_M(C[n][2]), f0(n, m)));

    FOR(i, 1, n) FOR_1(j, 0, m){
        INC(res, pdt(_I(2), sqr_M(i), sqr_M(n-i), C[n][i], f0(n-i, m-j), f0(i, j)));
        INC(res, pdt(i, n-i, C[n][i], sum(C[n-i][2], C[i][2]), f0(n-i, m-j), f0(i, j)));
    }

    #define i3 n-i1-i2
    #define j3 m-j1-j2

    FOR(i1, 0, n) FOR_1(j1, 0, m)
        FOR(i2, 0, n-i1+1) FOR_1(j2, 0, m-j1)
            INC(res, pdt(i1, sqr_M(i2), i3 , C[n][i1], C[n-i1][i2], f0(i3, j3), f0(i2, j2), f0(i1, j1)));

    return res;
}


int f(int n, int m, int k){
    if (k == 0) return f0(n, m);
    else if (k == 1) return f1(n, m);
    else return f2(n, m);
}

class KingdomAndCities {
public:
	int howMany(int n, int k, int m) {

	    ::n = n, ::m = m, ::k = k;

        FOR_1_C(i, 0, max(n, n*(n-1)/2)){
            C[i][0] = 1;REP_C(j, min(max(2, m), i)) C[i][j+1] = sum(C[i-1][j+1], C[i-1][j]);
        }

	    S[0][0] = A[0][0] = 1; REP_1(i, n) FOR_1_C(j, 0, min(m, C[i][2])){
            A[i][j] = S[i][j] = C[C[i][2]][j];
            FOR(ii, 1, i) FOR_1(jj, 0, j) DEC(A[i][j], pdt(C[i-1][ii-1], A[ii][jj], S[i-ii][j-jj]));
	    }

        return f(n, m, k);
	}
};

External link:

http://community.topcoder.com/stat?c=coder_room_stats&rd=15170&cr=22727863

Posted by xiaodao
Category: TopCoder