记录编号	581436	评测结果	AAAAAAAAAA
题目名称	支付宝	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.053 s
提交时间	2023-08-02 22:51:39	内存使用	4.05 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 210,M = 20010;
int n,m;
int w[N],c[N],tot,dp[M],ans[N],v[M*10];
struct made{
	int w,x;
}s[M*10];//存支票金额,和该金额是第几种支票 
void init(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)scanf("%d",&w[i]);
    for(int i = 1;i <= n;i++)scanf("%d",&c[i]);
    for(int i = 1;i <= n;i++){
        int p = 1;
        while(c[i] >= p){
            c[i] -= p;
            s[++tot].w = p * w[i];
            s[tot].x = i;//第i种支票 
            p <<= 1;
        }
        if(c[i] > 0){
            s[++tot].w = c[i] * w[i];
            s[tot].x = i;//第i种支票
        }//二进制拆分 
    }
    scanf("%d",&m);
}
void dfs(int x){
	if(x == 0)return;//边界 
	int i = v[x];//x的前驱 
	ans[s[i].x]/*x前驱的支票种类*/ += (s[i].w / w[s[i].x]);//加上有几种该类支票 
	dfs(x-s[i].w);//
}
int main(){
    freopen("pay.in","r",stdin);
    freopen("pay.out","w",stdout);
    init();
    memset(dp,0x3f,sizeof(dp));
    dp[0] = 0;
    for(int i = 1;i <= tot;i++){
        for(int j = m;j >= s[i].w;j--){
        	if(dp[j-s[i].w]+1 < dp[j]){//多重背包 
        		dp[j] = dp[j-s[i].w]+1;
        		if(!v[j])v[j] = i;//j的前驱 
        		if(j == m)v[j] = i;//j为m时要改变 
			}
        }
    }
    printf("%d\n",dp[m]);
    dfs(m);//从m深搜所有前驱 
    for(int i = 1;i <= n;i++){
    	printf("%d ",ans[i]);
	}
	printf("\n");
    
    return 0;
     
}