poj3181 (dp种类数+大数加法)
发布时间:2020-12-14 04:03:42 所属栏目:大数据 来源:网络整理
导读:点击打开链接 题意: 给你m和n,m表示有m元钱,n表示有n中钱币分别为1-n,求,m元钱最多组成的种类数。 dp[j]=dp[j]+dp[j-i]; 注意要用大数 #include"stdio.h"#include"string.h"#define N 1005int dp[N][N];int len[N];void add(int x,int y){int i;len[x]
点击打开链接 题意: 给你m和n,m表示有m元钱,n表示有n中钱币分别为1-n,求,m元钱最多组成的种类数。 dp[j]=dp[j]+dp[j-i]; 注意要用大数 #include"stdio.h" #include"string.h" #define N 1005 int dp[N][N]; int len[N]; void add(int x,int y) { int i; len[x]=len[x]>len[y]?len[x]:len[y]; int carry; carry=0; for(i=0;i<len[x];i++) { dp[x][i]=dp[x][i]+dp[y][i]+carry; carry=0; if(dp[x][i]>=10) { carry=dp[x][i]/10; dp[x][i]%=10; } } if(carry!=0) { dp[x][len[x]]=carry; len[x]++; } return ; } int main() { int n,m; int i,j; while(scanf("%d%d",&m,&n)!=-1) { memset(dp,sizeof(dp)); memset(len,sizeof(len)); dp[0][0]=1;len[0]=1; for(i=1;i<=n;i++) { for(j=i;j<=m;j++) { add(j,j-i); } } for(i=len[m]-1;i>=0;i--) printf("%d",dp[m][i]); printf("n"); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |