HDU 3591 The trouble of Xiaoqian

将 Xiaoqian可付的钱的值用多重背包的方式计算拼凑起来所需的最小硬币数，用完全背包的方式计算找钱的值的拼凑最小硬币数。然后再寻找最小值。

 

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> using namespace std; int dp1[20005], dp2[20005], t, v[105], r[105]; const int INF=1<<29; void deal1(int x) {int i;if(v[x]*r[x]>=20000){for(i=v[x];i<=20000;i++){dp1[i]=min(dp1[i],dp1[i-v[x]]+1);}}else{int k=1;while(k<r[x]){for(i=20000;i>=k*v[x];i--)dp1[i]=min(dp1[i],dp1[i-k*v[x]]+k);r[x]-=k;k*=2;}for(i=20000;i>=r[x]*v[x];i--)dp1[i]=min(dp1[i],dp1[i-r[x]*v[x]]+r[x]);} } void deal2(int x) {int i;for(i=v[x];i<=20000;i++){dp2[i]=min(dp2[i],dp2[i-v[x]]+1);} } int main() {int n, i, nc=0;while(scanf("%d%d",&n,&t)!=EOF){if(n==0&&t==0) break;for(i=0;i<n;i++)scanf("%d",&v[i]);for(i=0;i<n;i++)scanf("%d",&r[i]);dp1[0]=dp2[0]=0;for(i=1;i<=20000;i++)dp1[i]=dp2[i]=INF;for(i=0;i<n;i++)deal1(i);for(i=0;i<n;i++)deal2(i);int ans=INF;for(i=20000;i>=t;i--){if(dp1[i]!=INF&&dp2[i-t]!=INF)ans=min(ans,dp1[i]+dp2[i-t]);}printf("Case %d: ",++nc);if(ans==INF)printf("-1\n");elseprintf("%d\n",ans);}return 0; }

 

转载于:https://www.cnblogs.com/ink-syk/p/3315153.html

总结

以上是生活随笔为你收集整理的HDU 3591 The trouble of Xiaoqian的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。