AT_joisc2015_f题解
Kreado
·
·
题解
题目传送门。
思路
我们称一个员工的进出为一个事件。
我们不妨将所有事件按照事件发生的时间点排序，我们假设 i 为触发一个事件的员工，j 为下一个时间点触发事件的员工，考虑每种情况对答案（也就是大门锁的时间）什么时候有贡献，我们可以分成 4 类来讨论：
这样我们就转换成了一个图上问题，不难发现这个图是由若干条链组成的（因为每个员工只有两种状态），我们不妨将这些链组成一个大链，对这个链式序列 DP 即可。
记 val_i 表示 i 点权，val1_i 表示 i 到连接到的那个点的边权。
我们设 f_{i,j,0/1} 表示当前链的前面 i 个人，共有 j 把钥匙，第 i 个人是否有钥匙的最大贡献。
若第 i 个人没有钥匙，那么有 f_{i,j,0}=\max\{f_{i,j,0},f_{i-1,j,1},f_{i-1,j,0}\}。
若第 i 个人有钥匙，那么有 f_{i,j+1,1}=\max\{f_{i,j+1,1},f_{i-1,j,0}+val_i,f_{i-1,j,1}+val_i+val1_i\}
（这个边两端点都有 1，因此两点之间有边，所以要加上边权）
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int Maxn=2010;
int f[2][Maxn][2];
struct node{
int pos,id;
bool flg;
}a[Maxn<<2];
int n,m,k,tot,nxt[Maxn],val[Maxn],val1[Maxn];
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1,l,r;i<=n;i++){
scanf("%d%d",&l,&r);
a[++tot]=(node){l,i,0};
a[++tot]=(node){r,i,1};
}
sort(a+1,a+tot+1,[](const node x,const node y){return x.pos<y.pos;});
f[0][0][0]=(a[1].pos+m-a[tot].pos);
for(int i=1;i<tot;i++){
int w=a[i+1].pos-a[i].pos;
if(a[i].flg&&!a[i+1].flg) f[0][0][0]+=w;
if(a[i].flg&&a[i+1].flg) val[a[i+1].id]+=w;
if(!a[i].flg&&!a[i+1].flg) val[a[i].id]+=w;
if(!a[i].flg&&a[i+1].flg){
if(a[i+1].id==a[i].id) val[a[i].id]+=w;
else nxt[a[i+1].id]=a[i].id,val1[a[i].id]+=w;
}
}
int pre=0;
for(int i=1;i<=n;i++)
if(!val1[i]){
nxt[pre]=i;
while(nxt[pre]) pre=nxt[pre];
}
int tp=0;
for(int i=nxt[0];i;i=nxt[i]){
tp^=1;
for(int j=0;j<=k;j++){
for(int h=0;h<=1;h++){
if(!f[tp^1][j][h]) continue;
f[tp][j][0]=max(f[tp][j][0],f[tp^1][j][h]);
f[tp][j+1][1]=max(f[tp][j+1][1],f[tp^1][j][h]+val1[i]*h+val[i]);
f[tp^1][j][h]=0;
}
}
}
printf("%d\n",max(f[tp][k][0],f[tp][k][1]));
return 0;
}
```