随笔-141  评论-9  文章-3  trackbacks-0
USACO 2.3.2 Cow Pedigrees (DP)

/*
ID: lorelei3
TASK: nocows
LANG: C++
*/

#include <fstream>

using namespace std;

const int K = 105;
const int N = 205;
const int MOD = 9901;

int dp[K][N];
int s[K][N];

int k,n;

int main(){

    int i,j,m,c;

    ifstream in("nocows.in");
    ofstream out("nocows.out");

    in>>n>>k;

    dp[1][1]=1;

    for(i=2; i<=k; ++i){
        for(j=1; j<=n; j+=2)
            for(m=1; m<=j-1-m; m+=2){
                if(m==j-1-m)    c=1;
                else    c=2;

                dp[i][j] += c* ( dp[i-1][m]*s[i-2][j-1-m] +
                                dp[i-1][j-1-m]*s[i-2][m] +
                                dp[i-1][m]*dp[i-1][j-1-m] );
                dp[i][j] %= MOD;
            }
    
        for(j=0; j<=n; ++j){
            s[i-1][j] += dp[i-1][j] + s[i-2][j];
            s[i-1][j] %= MOD;
        }
    }

    out<<dp[k][n]<<endl;
    return 0;
}
posted on 2010-12-21 10:17 小阮 阅读(188) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮