题意:\(n\)个位置,每个位置有价值\(v_i\)和重量\(p_i\),要选出一些位置,如果要选位置\(i\),那么前面选的重量之和要为\(l_i\),后面选的重量之和要为\(r_i\),求一个方案使得价值和最大
这个限制很舒服,可以设\(f_i\)为从前面开始选,选第\(i\)个的最大价值,转移枚举前面的\(j\),如果能从\(j\)转移过来,根据条件,要求\(l_i=l_j+p_i\&\&r_i=r_j-p_i\),记个转移前缀就可以输出方案了
但是这样还不优,我们可以发现对于一个\(i\),只有\(l_j+p_j+r_j=l_i+p_i+r_i\)的\(j\)能够转移过来,于是可以把所有\(l_i+p_i+r_i\)相等的放在一组,每一组里,记\(f_k\)为前缀重量为\(k\)的最大价值,转移从前往后枚举\(i\),从\(f_{l_i}\)向\(f_{l_i+p_i}\)转移,这一组的答案应为\(f_{l_i+p_i+r_i}\)
代码贼丑,轻\(\mathfrak{D}\)qwq
#include<bits/stdc++.h>
#define il inline
#define re register
#define LL long long
#define ull unsigned long long
#define db double
#define eps (1e-7)
using namespace std;
const int N=200000+10,M=3000000+10;
il LL rd()
{
LL x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int f[M],hd[M],nt[N];
int n,a[N][4],ma;
int st[N],an[N],tt=0,pre[N],g[M];
int main()
{
n=rd();
for(int i=1;i<=n;i++)
{
a[i][0]=rd(),a[i][1]=rd(),a[i][2]=rd(),a[i][3]=rd();
int pp=a[i][1]+a[i][2]+a[i][3];
ma=max(ma,pp);
nt[i]=hd[pp],hd[pp]=i;
}
memset(f,-63,sizeof(f));
f[0]=0;
int ii=-1,ans=0,inf=f[1];
for(int h=0;h<=ma;h++)
{
if(!hd[h]) continue;
int st[N],tt=0;
for(int i=hd[h];i;i=nt[i]) st[++tt]=i;
for(int i=tt;i>=1;i--) f[a[st[i]][1]+a[st[i]][2]]=max(f[a[st[i]][1]+a[st[i]][2]],f[a[st[i]][2]]+a[st[i]][0]);
if(ans<f[h]) ans=f[h],ii=h;
for(int i=tt;i>=1;i--) f[a[st[i]][1]+a[st[i]][2]]=inf;
}
//printf("%d\n",ans);
if(ii>=0)
{
for(int i=hd[ii];i;i=nt[i]) st[++tt]=i;
for(int i=tt;i>=1;i--)
if(f[a[st[i]][1]+a[st[i]][2]]<f[a[st[i]][2]]+a[st[i]][0])
f[a[st[i]][1]+a[st[i]][2]]=f[a[st[i]][2]]+a[st[i]][0],pre[st[i]]=g[a[st[i]][2]],g[a[st[i]][1]+a[st[i]][2]]=st[i];
tt=0;
int nw=g[ii];
while(nw)
{
an[++tt]=nw,nw=pre[nw];
}
printf("%d\n",tt);
for(int i=tt;i>=1;i--) printf("%d ",an[i]);
}
else puts("0");
return 0;
}