一、题目
二、解法
把时间点排序，考虑每个时间段在什么条件下才会贡献，可以分成 (4) 种情况讨论（(i) 表示排序后这个点的人）：
- (i) 进 (i+1) 出，什么情况下都可以贡献。
- (i) 进 (i+1) 进，当且仅当 (i+1) 有钥匙才能开门，(i) 就会把门关上产生贡献。
- (i) 出 (i+1) 出，当且仅当 (i) 有钥匙才能关门，(i) 就会把门关上产生贡献。
- (i) 出 (i+1) 进，当且仅当两个人都有钥匙时 (i) 会在出去的时候把门关上，(i+1) 进来时能开门。
- ( t Otherwise)，门都会保持打开的状态，所以有没有钥匙都一定能合法。
考虑计算贡献，贡献 (1) 直接记录到答案中，贡献 (2,3) 记录在需要钥匙的那个人上，也就是这个人有钥匙就能产生贡献。贡献 (4) 记录在两个人之间的边上，表示两个人都有钥匙就能产生贡献。
这样变成一张图上选点最大化贡献的问题，但是这个图有特殊限制，考虑每个点最多连出去两条边并且不会有环，所以这张图就是若干条链。我们把这条链的端点串起来，这样就变成了序列问题，就可以直接 (dp) 了，设 (dp[i][j][0/1]) 表示前 (i) 个点中分配了 (j) 把钥匙，第 (i) 个人有还是没有钥匙，时间复杂度 (O(n^2))
三、总结
贡献法也能运用到规划问题中去，还是从小处入手，考虑贡献产生的条件即可，是无条件贡献？是点限制贡献？是边限制贡献？
#include <cstdio>
#include <algorithm>
using namespace std;
const int M = 4005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,t,w,ans,b[M],c[M],nxt[M],dp[2][M][M];
struct node
{
int x,id,fl;
bool operator < (const node &b) const
{
return x<b.x;
}
}a[2*M];
signed main()
{
n=read();m=read();k=read();
for(int i=1;i<=n;i++)
{
a[++t]=node{read(),i,0};
a[++t]=node{read(),i,1};
}
sort(a+1,a+1+t);
ans=a[1].x+m-a[t].x;
for(int i=1;i<t;i++)
{
int w=a[i+1].x-a[i].x;
if(a[i].fl && !a[i+1].fl) ans+=w;
if(!a[i].fl && !a[i+1].fl) c[a[i].id]+=w;
if(a[i].fl && a[i+1].fl) c[a[i+1].id]+=w;
if(!a[i].fl && a[i+1].fl)
{
if(a[i].id==a[i+1].id) c[a[i].id]+=w;
else nxt[a[i+1].id]=a[i].id,b[a[i].id]+=w;
}
}
int pr=0;
for(int i=1;i<=n;i++)
if(!b[i])
{
nxt[pr]=i;
for(;nxt[pr];pr=nxt[pr]);
}
dp[0][0][0]=ans;
for(int i=nxt[0];i;i=nxt[i])
{
w^=1;
for(int j=0;j<=k;j++)
for(int t=0;t<=1;t++)
{
if(!dp[w^1][j][t]) continue;//illegal states
dp[w][j][0]=max(dp[w][j][0],dp[w^1][j][t]);
dp[w][j+1][1]=max(dp[w][j+1][1],dp[w^1][j][t]+t*b[i]+c[i]);
dp[w^1][j][t]=0;
}
}
printf("%d
",max(dp[w][k][0],dp[w][k][1]));
}