题目传送门：http://codeforces.com/problemset/problem/28/D
题意：给你$N$个物品，每个物品有其价格$P_i$，之前必须要买的物品价格和$L_i$，之后必须要买的物品价格和$R_i$和价值$W_i$。试给出一种物品的选择方案，使得满足所有选择的物品的条件且选择物品的价值和最大（物品的选择顺序必须要与原来的顺序相同）。$N \leq 10^5 , P , L , R \leq 10^5 , W \leq 10^4$
像背包DP，所以就是背包DP（雾
我们能够发现从物品$i$转移到物品$j$的充要条件是：$R_i=R_j+P_j$且$L_i+P_i=L_j$。将二式相加得$P_i+L_i+R_i=P_j+L_j+R_j$，也就是说$P+L+R$相等的物品才能够互相转移。所以我们可以考虑使用$vector$存每个$P+L+R$对应的物品，对于每个组跑一次DP。因为每一个物品的转移只能从$L$到$L+P$，所以转移是$O(1)$的，所以DP总复杂度为$O(n)$。注意DP数组的清空推荐使用还原而不是memset，这样还原的复杂度才是$O(n)$。
获得了最大的价值之后，对对应的那一个组别再跑一遍DP，跑出方案。方案的记录可以通过记录某一个物品选择前最后选择的物品来实现。总复杂度为$O(n)$。
注意每一个组别一定要有始有终（也就是选择的物品必须要有$L=0$与$R=0$的物品，也可以通过这一个来剪一些枝降低常数）
关于输出方案其实可以使用递归，但是因为本机会爆栈所以用循环+vector输出
#include<bits/stdc++.h>
#define MAXN 3000010
#define MAXM 200010
using namespace std;
inline int read(){
;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return a;
}
struct thing{
int w , p , l , r , ind;
}now;
vector < thing > v[MAXN];
vector < int > anss;
, maxDir;
bool haveEnd[MAXN];
void out(int dir){
){
anss.push_back(v[maxDir][dir].ind);
dir = last[dir];
}
; i >= ; i--)
printf("%d " , anss[i]);
}
int main(){
int N = read();
; i <= N ; i++){
now.w = read();
now.p = read();
now.l = read();
now.r = read();
now.ind = i;
){
cnt[now.p + now.l + now.r]++;
v[now.p + now.l + now.r].push_back(now);
)
haveEnd[now.p + now.l + now.r] = ;
}
}
memset(maxPri , -0x3f , sizeof(maxPri));
maxPri[] = ;
; i <= ; i++)
if(cnt[i] && haveEnd[i]){
; j < cnt[i] ; j++)
maxPri[v[i][j].l + v[i][j].p] = max(maxPri[v[i][j].l + v[i][j].p] , maxPri[v[i][j].l] + v[i][j].w);
if(maxN < maxPri[i]){
maxN = maxPri[i];
maxDir = i;
}
; j < cnt[i] ; j++)
maxPri[v[i][j].l + v[i][j].p] = -0x3f3f3f3f;
}
memset(last , - , sizeof(last));
memset(k , - , sizeof(k));
; j < cnt[maxDir] ; j++)
if(maxPri[v[maxDir][j].l + v[maxDir][j].p] < maxPri[v[maxDir][j].l] + v[maxDir][j].w){
maxPri[v[maxDir][j].l + v[maxDir][j].p] = maxPri[v[maxDir][j].l] + v[maxDir][j].w;
last[j] = k[v[maxDir][j].l];
k[v[maxDir][j].l + v[maxDir][j].p] = j;
ans[v[maxDir][j].l + v[maxDir][j].p] = ans[v[maxDir][j].l] + ;
}
printf("%d\n" , ans[maxDir]);
out(k[maxDir]);
;
}