1221:UNIMODAL PALINDROMIC DECOMPOSITIONS

PKU

keyword

動的計画法　整数分割　C++

概要

整数N(<300位？)が与えられる。このとき、Nを数列の和で表す方法は何通りあるか。ただし、数列は対象(a_1 == a_n, a_2==a_n-1...)で、折り返す部分は非減少列である。
数列が偶数と奇数の場合をそれぞれ別個に求める。dp[N][数列の上界][偶数か奇数か]の3状態で、計算量はO(n^2)位。

int main(){
    ll dp[300][300][2];
    int i, j, k;
    REP(i,300)REP(j,300)REP(k,2) dp[i][j][k] = 0;

    for(i=1; i<300; i++){
        dp[i][i][1] = 1;
        for(j=1; j<i; j++){
            dp[i][j][1] += dp[i-j][j][0];
            if((i&1)==0 && (j&1)==0) dp[i][j>>1][0] += dp[i-j][(j>>1)][0];
        }
        if(!(i&1)) dp[i][i>>1][0]++;

        for(j=1;j<300;j++){
            dp[i][j][0] += dp[i][j-1][0];
            dp[i][j][1] += dp[i][j-1][1];
        }
    }

    int n;
    while(scanf("%d",&n)){
        if(!n) break;
        printf("%d %lld\n", n, dp[n][299][0] + dp[n][299][1]);
    }

    return 0;
}