分析
多重背包优化，输出方案
二进制优化 / 单调队列优化
输出方案只需要记录是否转移，用bool类型存
这题好像卡空间
代码
1.二进制优化
1 /************************ 2 User:Mandy.H.Y 3 Language:c++ 4 Problem:luogu 5 Algorithm: 6 Date:2019.8.30 7 ************************/ 8 9 #include<bits/stdc++.h> 10 11 using namespace std; 12 13 const int maxn = 205; 14 const int maxk = 2e4 + 5; 15 int b[maxn],c[maxn],new_b[4005],new_c[4005],new_id[4005]; 16 int dp[maxk],ans[maxn]; 17 int n,k,cnt; 18 bool vis[4005][maxk]; 19 20 template<class T>inline void read(T&x){ 21 x = 0;bool flag = 0;char ch = getchar(); 22 while(!isdigit(ch)) flag |= ch == '-',ch = getchar(); 23 while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar(); 24 if(flag) x = -x; 25 } 26 27 template<class T>void putch(const T x){ 28 if(x > 9) putch(x / 10); 29 putchar(x % 10 | 48); 30 } 31 32 template<class T>void put(const T x){ 33 if(x < 0) putchar('-'),putch(-x); 34 else putch(x); 35 } 36 37 void file(){ 38 freopen("3423.in","r",stdin); 39 freopen("3423.out","w",stdout); 40 } 41 42 void readdata(){ 43 read(n); 44 for(int i = 1;i <= n; ++ i) read(b[i]); 45 for(int i = 1;i <= n; ++ i) read(c[i]); 46 read(k); 47 } 48 49 void work(){ 50 for(int i = 1;i <= n; ++ i){ 51 c[i] = min(c[i],k/b[i]); 52 for(int j = 1;j <= c[i]; j <<= 1){ 53 new_b[++cnt] = b[i] * j; 54 new_c[cnt] = j; 55 new_id[cnt] = i; 56 c[i] -= j; 57 } 58 59 if(c[i]){ 60 new_b[++cnt] = b[i] * c[i]; 61 new_c[cnt] = c[i]; 62 new_id[cnt] = i; 63 c[i] = 0; 64 } 65 } 66 memset(dp,0x3f3f3f3f,sizeof(dp)); 67 dp[0] = 0; 68 for(int i = 1;i <= cnt; ++ i){ 69 for(int j = k;j >= new_b[i]; -- j){ 70 if(dp[j] > dp[j - new_b[i]] + new_c[i]){ 71 dp[j] = dp[j - new_b[i]] + new_c[i]; 72 vis[i][j] = 1; 73 } 74 } 75 } 76 77 put(dp[k]); 78 putchar(' '); 79 int i = cnt,j = k; 80 while(i >= 1){ 81 if(vis[i][j]) 82 j = j - new_b[i],ans[new_id[i]] += new_c[i]; 83 --i; 84 } 85 for(int i = 1;i <= n; ++ i){ 86 put(ans[i]); 87 putchar(' '); 88 } 89 } 90 91 int main(){ 92 // file(); 93 readdata(); 94 work(); 95 return 0; 96 }