SRM 585

250

高さがhの二分木が与えられる。枝分かれのない辺の集合に分割するとき、その集合の個数の最小値(を定数で割ったもの)を求める。

分かりやすく言うと、一筆書きを何回か行って、高さhの二分木をつくるのに必要な回数の最小値を求める。

証明はできませんが、葉の方から順に考えて、高さが1の二分木に分けていけばよい。

class TrafficCongestion {
public:
	int theMinCars( int H ) {
		ll ans = 0;
		for(ll i = (H+1)&1,r = 1+i; i < H; i+=2){
			ans = (ans+r)%mod;
			r = (r*4)%mod;
		}
		return (ans+((H+1)&1))%mod;
	}
};

500

1～36までの数字が書かれたカードがそれぞれ0枚以上36枚以下ある。(1は必ず1枚はあり、途中の数字だけないということもない。)
カードをすべて並べてできる数列のうち、増加数列(c[0] < c[1] < ...)となるような数列)K個つなげてでき、かつ、それより少ない個数の増加数列をつなげても作れない数列が何通りあるかを求める。

カードの数字が小さいものから並べていき、間にそれより大きい数字のカードを入れていくようにして考えると解ける。
必要な増加数列の個数が増えるようにカードを挿入するときに、重複組み合わせの考え方が必要なことに注意する。

int mod = 1000000007;
ll dp[50][3000],C[2000][2000];

class LISNumber {
public:
	int count( vector <int> s, int K ) {
		memset(dp,0,sizeof(dp));
		for(int i = 0; i < 2000; i++)C[i][0] = C[0][i] = 1;
		for(int i = 1; i < 2000; i++)
			for(int j = 1; j < 2000; j++)
				C[i][j] = (C[i][j-1]+C[i-1][j])%mod;
		ll M = s[0];
		int n = s.size();
		dp[0][s[0]] = 1;
		for(ll i = 1; i < n; i++){
			ll V = s[i];
			for(ll j = s[0]; j <= min((ll)K,M); j++){
				for(ll k = 0; k <= min(V,j); k++){
					dp[i][j+V-k] = (dp[i][j+V-k]+((dp[i-1][j]*C[j-k][k])%mod)*C[M+k-j][V-k]%mod)%mod;
				}
			}
			M += V;
		}

		return dp[n-1][K];
	}
};

o-- 199.31pts
1489 -> 1521