P3423 [POI2005] BAN-Bank Notes

 [POI2005] BAN-Bank Notes - 洛谷

核心思路

二进制优化背包

dp[u] 表示要达到 u 面值的币数。

AC 代码

#include<bits/stdc++.h>
using namespace std;
struct bag{int v,w,k;
}b[3211];
/*
v[i]来表示第i个包的金币数；w[i]来表示第i个包的金币价值；k[i]来表示第i个包的金币面值编号；
*/
int tot;
void buildbag(int v,int w,int k){b[++tot] = (bag){v,w,k};
}
int dp[20001],n,m,v[20001],c,sum[20001];
bool from[3211][20001];
int main(){memset(dp,0x3f,sizeof(dp));dp[0] = 0;register int i,ii;cin>>n;for(int i = 1;i <= n;i++){cin>>v[i];}for(int i = 1;i <= n;i++){int c;cin>>c;for(ii = 1;c >= ii;c-=ii,ii <<= 1){buildbag(ii,ii*v[i],i);}if(c)buildbag(c,c*v[i],i);}cin>>m;for(int i = 1;i <= tot;i++){for(ii = m;ii >= b[i].w;ii--){int s = dp[ii-b[i].w]+b[i].v;if(s < dp[ii]){from[i][ii] = 1;dp[ii] = s;}}}cout<<dp[m]<<endl;int s = m,k = dp[m];for(i = tot;k;){while(!from[i][s])i--;k-=b[i].v,sum[b[i].k] += b[i].v,s-=b[i].w;i--;}for(int i = 1;i < n;i++){cout<<sum[i]<<" ";}cout<<sum[n];return 0;
}