//事实证明用dfs绝对超时了 = =
//用动态规划,dp[i][j]表示前i个数可以组合成j的个数
//若j-i>=0    dp[i][j]=dp[i-1][j]+dp[i-1][j-i]
//这个可以理解为前i-1个数可以组合成j和前i-1个数可以组合成j-i两种情况
//否则的话    dp[i][j]=dp[i-1][j];
//初始化状态 dp[1][0]=dp[1][1]=1;
//题目链接 http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2326
#include <stdio.h>

#define N 40
#define M 450

int n;
unsigned int dp[N+5][M];

void DP(){
    int i,j;
    dp[1][1]=dp[1][0]=1;
    for(i=2;i<=n;i++){
        for(j=0;j<=n*(n+1)/4;j++)
            if(j-i>=0)
                dp[i][j]=dp[i-1][j]+dp[i-1][j-i];
            else
                dp[i][j]=dp[i-1][j];
    }
}

int main(){
    while(scanf(“%d”,&n)!=EOF){
        if((n*(n+1))%4)
            printf(“0\n”);
        else{
            DP();
            printf(“%u\n”,dp[n][n*(n+1)/4]/2);
        }
    }
    return 0;
}

 

发表评论

电子邮件地址不会被公开。

Post Navigation