Miku

仍然是要优化的，但是输出方案是非常恶心的

一维爆炸，以下为二进制优化做法

关键是如果最后到着找方案的话，就比如说样例

5的最少方法就是一个5，但是因为dp的顺序是逆序。会把10指向5，然后5指向0

、？？，但是只有一个啊。所以不能倒序

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=200001;
int cnt;
int num[maxn],ca[maxn];
int num1[maxn],ca1[maxn];
int dp[maxn];
int k;
int aimm,n;
int ans[maxn];
int ord[maxn];
int used[maxn];
int sum;
bool tu[3010][20010];
int main(){
    memset(dp,0x7f,sizeof(dp));
    dp[0]=0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&ca[i]);
        ord[ca[i]]=i;
    }
    for(int i=1;i<=n;++i){
        scanf("%d",&num[i]);
    }
    scanf("%d",&aimm);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=num[i];j=j<<1){
            cnt++;
            num1[cnt]=j;
            ca1[cnt]=j*ca[i];
            num[i]-=j;
            ord[cnt]=i;
        }
        if(num[i]){
            cnt++;
            num1[cnt]=num[i];
            ca1[cnt]=num[i]*ca[i];
            ord[cnt]=i;
        }
    }
    for(int i=1;i<=cnt;++i){
        for(int j=aimm;j>=ca1[i];--j){
            if(dp[j]>dp[j-ca1[i]]+num1[i]){
                dp[j]=dp[j-ca1[i]]+num1[i];
                tu[i][j]=1; 
            }
        }
    } 
    cout<<dp[aimm]<<endl;
    while(aimm){
        while(!tu[cnt][aimm]&&cnt) --cnt;//是谁变成了aimm？
        //当然，肯定是后面的变前面的 
        aimm-=ca1[cnt];//去掉贡献 
        ans[ord[cnt]]+=num1[cnt];
        --cnt;//接着找 
    }
    for(int i=1;i<=n;++i){
        cout<<ans[i]<<" ";
    }
    return 0;
}