题意简述
有 \(2m+1\) 种物品，体积分别为 \(-m\sim m\)，每种物品有 \(a_i\) 个。
你需要选出尽可能多数量的物品，使得物品体积和为 \(l\)。
\(m\le 300,a_i,|l|\le 10^{18}\)
分析
此题属于“背包容量极大，物品体积极小”的特殊背包问题。
考虑背包问题的经典错误贪心：按照性价比降序排序取。错误原因是，这个方案可能会浪费一些背包容量，使得我们可以通过扔出一些物品再加入一些别的物品充分利用背包容量，从而最大化价值。
但此题容量极大，也就是说，背包容量“不怕浪费”！我们考虑前面按照性价比贪心取东西直到背包放不下了。但此时我们遇到了相同的问题：我们还是浪费了一些背包容量。
考虑在贪心出来的结果上进行常规背包 DP。将取过的物品的价值和体积取反，表示撤销该物品，没取过的物品不变。设 \(f_{i}\) 表示在贪心的基础上选取的物品体积和为 \(i\) 的最大价值，注意 \(i\) 在此定义下可以为负。
发掘性质：
- 令贪心后选的物品体积总和为 \(L\)，则 \(L\in (l-m,m]\)，显然，否则贪心不成立。
- 存在一种最优方案使得每次取完物品/反悔物品后物品的总体积在 \([l-m,l+m]\)，因为最终的总体积落在 \(l\)，所以我们可以在 \(l'<l\) 时加入物品，在 \(l'>l\) 时加入反悔物品，通过调整使其满足条件。
- 在贪心基础上我们会选择至多 \(2m\) 个物品，因为根据上一条性质，每次选完物品后的体积落在 \([l-m,l+m]\) 内，而一定不会存在某个体积会被重复到达且更优的情况（否则中间这段就相当于不消耗任何体积而白嫖了更多的价值，此时我们在贪心的基础上用这种方案白嫖会使得贪心方案更优，使贪心不成立）。而区间内一共就 \(2m\) 种体积。
- 根据第三条性质，我们直接把背包容量开到 \([-m^2,m^2]\) 做常规 DP 即可，视多重背包的实现复杂度三方或三方对数。
- 代码三方对数。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#include<cassert>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0);
#define OTIE cout.tie(0);
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("impossible")
#define P__ puts("")
#define PU puts("--------------------")
#define P0 puts("0")
#define popc __builtin_popcount
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=d)
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=d)
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
#define int long long
//#define int __int128
using namespace std;
typedef long long i64;
bool greating(int x,int y){return x>y;}
bool greatingll(long long x,long long y){return x>y;}
inline int rd(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
inline void write(int x,char ch='\0'){
if(x<0){x=-x;putchar('-');}
int y=0;char z[40];
while(x||!y){z[y++]=x%10+48;x/=10;}
while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=305,maxm=1e6+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,m,l;
int a[maxn],b[maxn];
int c[maxn],d[maxn];
int f[maxm];
void ins(int c,int v,int w){
if(v>0){
for(int j=1;j<=c;c-=j,j<<=1){
per(i,2*m,j*v)f[i]=max(f[i],f[i-j*v]+j*w);
}
if(c){
per(i,2*m,c*v)f[i]=max(f[i],f[i-c*v]+c*w);
}
}else{
v=-v;
for(int j=1;j<=c;c-=j,j<<=1){
rep(i,0,2*m-j*v)f[i]=max(f[i],f[i+j*v]+j*w);
}
if(c){
rep(i,0,2*m-c*v)f[i]=max(f[i],f[i+c*v]+c*w);
}
}
}
void solve_the_problem(){
n=rd(),m=n*n,l=rd();
int res=0;
per(i,n,1)a[i]=rd(),l+=a[i]*i,res+=a[i];
res+=rd();
rep(i,1,n)b[i]=rd();
if(l<0)return (void)PW;
rep(i,1,n){
if(l>=b[i]*i)l-=b[i]*i,res+=b[i],d[i]=b[i];
else{d[i]=l/i,res+=d[i],l-=d[i]*i;break;};
}
per(i,n,1){
if(l>=a[i]*i)l-=a[i]*i,res-=a[i],c[i]=a[i];
else{c[i]=l/i,res-=c[i],l-=c[i]*i;break;}
}
mem(f,0xc0);
f[m]=res;
rep(i,1,n){
ins(c[i],-i,1);
ins(a[i]-c[i],i,-1);
ins(d[i],-i,-1);
ins(b[i]-d[i],i,1);
}
if(l>m||f[l+m]<0)PW;
else write(f[l+m]);
}
bool Med;
signed main(){
// freopen(".in","r",stdin);freopen(".out","w",stdout);
// fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);
int _=1;while(_--)solve_the_problem();
}
/*
*/