首页 > 代码库 > 【简单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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。