思路:
题目的意思:手表的价格为m元,要在硬币中选择一些硬币构成多少种不同的总价值p(且使其总价值p在(1->m)之间)
AC代码:
#include<stdio.h> #include<string.h> int dp[100005],c[105],v[105]; int m; void CompletePack(int c,int w) { int i; for(i=c;i<=m;i++) if(dp[i]<dp[i-c]+w) { dp[i]=dp[i-c]+w; } } void ZeroOnePack(int c,int w) { int i; for(i=m;i>=c;i--) if(dp[i]<dp[i-c]+w) { dp[i]=dp[i-c]+w; } } void MultiPack(int c,int w,int amount) { int k; if(c*amount>m) { CompletePack(c,w); return ; } k=1; while(k<amount) { ZeroOnePack(k*c,k*w); amount-=k; k*=2; } ZeroOnePack(amount*c,amount*w); } int main() { int n; int i,j; int count; int flag[100005]; while(scanf("%d%d",&n,&m)!=-1&&(n+m)) { for(i=1;i<=n;i++) scanf("%d",&v[i]); for(i=1;i<=n;i++) scanf("%d",&c[i]); memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) MultiPack(v[i],v[i],c[i]); j=1; for(i=m;i>=1;i--) if(dp[i])flag[j++]=dp[i];/*把在1->m之间的构成的价值不为0的存入标记数组*/ count=j-1;/*可能构成的最大的价格总数,因为可能含有相同的价格*/ for(i=2;i<=j-1;i++) if(flag[i]==flag[i-1])count--;/*因为flag数组本身是有序的,只要判断相连之间是否相等,相等则减1*/ printf("%d\n",count); } return 0; }