传送门
显然不能直接写多重背包。
这题可以用二进制拆分/单调队列优化（感觉二进制好写）。
所谓二进制优化，就是把1~c[i]拆分成20,21,...2t,c[i]−2t+1+1" role="presentation" style="position: relative;">20,21,...2t,c[i]−2t+1+120,21,...2t,c[i]−2t+1+1的组合。
这样物品总个数就变成了∑log(c[i])" role="presentation" style="position: relative;">∑log(c[i])∑log(c[i])
于是可以跑01背包水过去。
代码：
#include<bits/stdc++.h>
#define K 20005*15
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,a[K],b[K],k,c[K],d[K],dp[K],tot=0;
int main(){
n=read();
for(int i=1;i<=n;++i)b[i]=read();
for(int i=1;i<=n;++i)a[i]=read();
k=read();
for(int i=1;i<=n;++i){
int pos=0;
for(int j=0;(1<<j)<=a[i];++j)c[++tot]=b[i]*(1<<j),d[tot]=1<<j,a[i]-=(1<<j);
if(a[i])c[++tot]=b[i]*a[i],d[tot]=a[i];
}
memset(dp,0x3f,sizeof(dp)),dp[0]=0;
for(int i=1;i<=tot;++i)for(int j=k;j>=c[i];--j)dp[j]=min(dp[j],dp[j-c[i]]+d[i]);
cout<<dp[k];
return 0;
}