【CF480D】Parcels
题意：有一个栈，有n个物品，每个物品可以选或不选。如果选了第i个物品，则获得$v_i$的收益，且第i个物品必须在$in_i$时刻入栈，$out_i$时刻出栈。每个物品还有一个重量$w_i$和载荷$s_i$，栈底的载荷为m，你需要时刻保证一个物品（或栈底）上方的所有物品的重量之和不超过这个物品的载荷。问最大收益。
$n\le 500,m\le 1000$
题解：先将所有物品按右端点从小到大，如果右端点相同则左端点从大到小排列。设f[i][j]表示选择第i个物品，i及i上方的物品总重为j时这些物品的最大收益。在求f[i][j]时，我们需要扫一遍i上面的所有物品，为此我们引入辅助数组g[i]（求不同的f[i][j]用的g[i]是不同的）（i是位置不是物品号），表示位置i前面的物品的最大总收益。因为我们已经排好序了，所以在新来一个物品时只需要g[out]=max(g[out],g[in]+f[x][..])即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int f[510][1010],g[1010];
int n,m;
struct node
{
int l,r,w,v,s;
}p[510];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
bool cmp(const node &a,const node &b)
{
return (a.r==b.r)?(a.l>b.l):(a.r<b.r);
}
int main()
{
n=rd(),m=rd();
int i,j,k,l;
for(i=1;i<=n;i++) p[i].l=rd(),p[i].r=rd(),p[i].w=rd(),p[i].s=min(m,rd()),p[i].v=rd();
sort(p+1,p+n+1,cmp);
p[n+1].l=0,p[n+1].r=n<<1,p[n+1].s=m;
for(i=1;i<=n+1;i++) for(k=p[i].w;k<=m;k++)
{
g[l=p[i].l]=0;
for(j=1;j<i;j++) if(p[j].l>=p[i].l)
{
while(l<p[j].r) l++,g[l]=g[l-1];
g[l]=max(g[l],g[p[j].l]+f[j][min(k-p[i].w,p[i].s)]);
}
f[i][k]=g[l]+p[i].v;
}
printf("%d",f[n+1][m]);
return 0;
}