SRM585 Div1

コーナーケース氏死んでくれ〜〜　ちゃんと制約読もう

easy
まあ色んな方法あるが自分は下から取っていくイメージ

#define MOD (1000000007LL)
ll p[1000010];
ll r[1000010];

class TrafficCongestion{
    public:
	int theMinCars(int treeHeight){
	    int h = treeHeight;
	    p[0] = 1LL; p[1] = 2LL;
	    for(int i = 2; i <= 1000000; ++i) p[i] = p[i-1] * 2LL % MOD;

	    if(h == 0) return 1;
	    if(h == 1) return 1;
	    
	    r[0] = 1;
	    r[1] = 1;
	    for(int i = 2; i <= h; ++i) r[i] = (p[i-1] + r[i-2]) % MOD;
	    
	    return (int)r[h];
	}
};

med
自明にdpだが式が少し難しい。左から見ていって、新しい数をそれまであった列に挿入していくイメージで考えると、strictly increasingな末尾に挿入すればLISnumberがそのままで、そうでない所に挿入すれば+1されることに気付くと、よくある数え上げdpになる。

#define MOD (1000000007LL)

int n;
ll comb[1310][1310];
ll dp[40][1310];

void pre(){
    comb[0][0] = 1LL;
    comb[1][0] = comb[1][1] = 1;
    for(int i = 2; i <= 1300; ++i){
	comb[i][0] = comb[i][i] = 1;
	for(int j = 1; j < i; ++j) comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD; 
    }
}

class LISNumber{
    public:
	int count(vector <int> cardsnum, int K){
	    vector<int> a = cardsnum;
	    n = (int)a.size();
	    pre();
	    
	    int s = a[0];
	    dp[1][a[0]] = 1;
	    
	    for(int i = 1; i < n; ++i){		
		s += a[i];
		for(int j = 1; j <= s; ++j){
		    for(int k = max(1, j - a[i]); k <= min(j, s); ++k){
			if(a[i] + k - j < 0 || a[i] - j > 1) continue;
			dp[i+1][j] += (dp[i][k] * comb[k][a[i] + k - j]) % MOD * comb[s - k][j - k];
			dp[i+1][j] %= MOD;
		    }
		}
	    }
	    
	    return (int)dp[n][K];    
	}
};