首页 > 代码库 > 【简单dp】 poj 2346

【简单dp】 poj 2346

题意:给定一个N 求一共有多少个N位数     前N/2个数的和等于后N/2个数的和
思路:令F[i][j] 为sum值为j的i位数的个数
则问题转化成 求 sum(F[n/2][j] * F[n/2][j])
注意 如果n为奇数要乘以10.

 

#include <iostream>#include <cstdio>#include <memory.h>using namespace std;int dp[6][100];int main(){//    freopen("in.txt","r",stdin);    memset(dp,0,sizeof(dp));    int i,j,k,n;    dp[0][0]=1;    for(i=1;i<=5;i++)        for(j=0;j<=50;j++)        {            for(k=0;k<=9;k++)                if(j>=k)                    dp[i][j]+=dp[i-1][j-k];        }    while(cin>>n)    {        long long ans=0;        for(i=0;i<=50;i++)            ans+=(dp[n/2][i]*dp[n/2][i]);        if(n&1)            ans*=10;        cout<<ans<<endl;    }    return 0;}

 

【简单dp】 poj 2346