Codeforces Contest 958 problem E2 Guard Duty (medium) —— DP求取k个区间，区间长度最小

This way

题意：

给你一些时刻，有k个客人，每个客人都要在某一个时刻进来出去，每次只能招待一个客人，且一个客人出去的时候另一个人不能进来。问你最少接待客人的时间是多少。

题解：

对于这4个点，如果一个人占用了中间两个点的话，那么剩下两个点就有可能用不到了，那么最多的情况就是需要k4个点，需要哪些点呢，也就是间隔最小的那些，我们处理出来之后，最多也就是20000个点，在5000，时间复杂度够了，但是开20000*5000的数组空间复杂度会爆炸，但是我们发现，对于枚举到的位置，只有两种情况，要么取要么不取，如果取的话，会从i-2那里转移过来，状态转移方程为

dp[j+1][2]=min(dp[j+1][2],dp[j][0]+a[i]-a[i-1]);

否则就是从上一个点转移过来，状态转移方程为

dp[j][2]=min(dp[j][2],dp[j][1]);

#include<bits/stdc++.h> using namespace std; int dp[5005][3]; struct node { int len,x,y; bool operator< (const node& a)const { return len<a.len; } }; int a[500005]; vector<node>vec; map<int,int>vis; int main() { int n,k; scanf("%d%d",&k,&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); for(int i=2;i<=n;i++) vec.push_back((node){a[i]-a[i-1],a[i-1],a[i]}); sort(vec.begin(),vec.end()); int all=0; for(int i=0;all<=k*2*2&&i<vec.size();i++) { if(!vis.count(vec[i].x)) vis[vec[i].x]=1,a[++all]=vec[i].x; if(!vis.count((vec[i].y))) vis[vec[i].y]=1,a[++all]=vec[i].y; } sort(a+1,a+1+all); for(int i=0;i<=k;i++) for(int j=0;j<=2;j++) dp[i][j]=1e9+1; dp[0][0]=dp[0][1]=0; int mi=1e9+1; for(int i=2;i<=all;i++) { for(int j=0;j<=min(k,i/2);j++) { dp[j+1][2]=min(dp[j+1][2],dp[j][0]+a[i]-a[i-1]); dp[j][2]=min(dp[j][2],dp[j][1]); if(j==k) mi=min(mi,dp[j][2]); } for(int j=0;j<=min(i/2,k);j++) { dp[j][0]=dp[j][1]; dp[j][1]=dp[j][2]; dp[j][2]=1e9+1; } } printf("%d\n",mi); return 0; }