题目描述
link
有 \(n\) 种牌，第 \(i\) 种有数量 \(c_i\)，每张消耗辉星 \(p_i\)、能量 \(v_i\)，基础伤害 \(s_i\)，且每打出 \(l_i\) 张额外造成 \(b_i\) 点伤害（累积触发）。你有 \(m\) 辉星、\(k\) 能量，求最大总伤害。
\(T \le 3,\ n \le 200,\ m,k \le 300,\ p_i,v_i,s_i,c_i,b_i \le 10^6,\ l_i \le 10^6\)（可为 \(0\)），所有输入非负。
解题思路
这是一个多重背包问题，但是对于 \(l_i\) 张的额外伤害有点难以处理，于是我们考虑将每 \(l_i\) 张是做一个整块，对这些块进行二进制分组。在对剩下 \(l_i-1\) 进行另外的二进制分组，这样就可以表示出每种选择方案了。
但是这样做有个问题，假设整块个数 \(cnt\)，很有可能你取满了 \(cnt\) 个整块，但是剩下还剩 \(r=n \% l_i\)，你没法取到 \(l_i-1\)，所以要分开考虑，先对 \(cnt-1\) 个整块进行上述操作，在对剩下的进行二进制分组处理，具体来说，剩下的数 \(0\sim r\)，此时前面的 \(cnt*l_i\) 个数我们必须取，我们需要先将 dp 数组先提前算上前面的数的影响。
具体实现参考代码。
还有单调队列的做法，有空可以想想。
code
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define out() (cout << "sb\n")const int N=205*40,M=305;int ccc,T,n,m,K;
ll f[M][M],g[M][M];
struct nd{ll p,v,s,c,l,b;int id;
}a[N],temp[N],b[N];signed main(){// system("fc .out .out");// freopen("ex_remember5.in","r",stdin);// freopen("remember.out","w",stdout);IOScin>>ccc>>T;while(T--){memset(f,0,sizeof(f));memset(g,0,sizeof(g));cin>>n>>m>>K;for(int i=1;i<=n;i++) {int p,v,s,c,l,b;cin>>p>>v>>s>>c>>l>>b;a[i]={p,v,s,c,l,b,i};}for(int i=1;i<=n;i++){ //枚举第 $i$ 个数int ta=0,tb=0;int l=a[i].l;int t=a[i].c/l;nd x;if(t==0){x=a[i];int sum=0,tot=0;for(int j=1;sum+j<=x.c;j<<=1){sum+=j;b[++tot]=x;b[tot].s*=j, b[tot].p*=j, b[tot].v*=j;}int temp=x.c-sum;if(temp) {b[++tot]=x;b[tot].s*=temp, b[tot].p*=temp, b[tot].v*=temp;}for(int id=1;id<=tot;id++){x=b[id];for(int j=m;j>=x.p;j--)for(int k=K;k>=x.v;k--)f[j][k]=g[j][k]=max(f[j][k],f[j-x.p][k-x.v]+x.s);}continue;}int tt=0;temp[++tt]={a[i].p*l, a[i].v*l, a[i].s*l+a[i].b, t-1,0,0,i};temp[++tt]=a[i], temp[tt].c=l-1;int tot=0;for(int _=1;_<=tt;_++){x=temp[_];int sum=0;for(int j=1;sum+j<=x.c;j<<=1){sum+=j;b[++tot]=x;b[tot].s*=j, b[tot].p*=j, b[tot].v*=j;}int temp=x.c-sum;if(!temp) continue;b[++tot]=x;b[tot].s*=temp, b[tot].p*=temp, b[tot].v*=temp;}for(int id=1;id<=tot;id++){x=b[id];for(int j=m;j>=x.p;j--)for(int k=K;k>=x.v;k--)f[j][k]=max(f[j][k],f[j-x.p][k-x.v]+x.s);}x=a[i];x.c=a[i].c%l;tot=0;int num=t*l;ll pp=num*x.p,vv=num*x.v,ss=t*x.b+num*x.s;int sum=0;b[++tot]={0};for(int j=1;sum+j<=x.c;j<<=1){sum+=j;b[++tot]=x;b[tot].s*=j, b[tot].p*=j, b[tot].v*=j;}int temp=x.c-sum;if(temp){b[++tot]=x;b[tot].s*=temp, b[tot].p*=temp, b[tot].v*=temp;}for(int j=m;j>=pp;j--)for(int k=K;k>=vv;k--)g[j][k]=g[j-pp][k-vv]+ss;for(int id=1;id<=tot;id++){x=b[id];for(int j=m;j>=pp+x.p;j--)for(int k=K;k>=vv+x.v;k--)g[j][k]=max(g[j][k],g[j-x.p][k-x.v]+x.s);}for(int j=0;j<=m;j++)for(int k=0;k<=K;k++)f[j][k]=g[j][k]=max(f[j][k],g[j][k]); //背包合并}cout<<f[m][K]<<"\n";}return 0;
}
总结
这道题赛时想到了，但是没有敲出来，并且后来调试了非常久。并且是一道背包变种，以后可以回来练练码力。