题解 P4182 【[USACO18JAN]Lifeguards P】

好吧，自己考虑的时候没想过要开多个单调队列来优化dp。。。 首先，如果一个区间被其他区间包含的话，很明显，它被删除也没影响。所以我们先按左节点排序，去除那些包含的区间，然后对接下来有序的区间进行dp。 dp[i][j]表示前i个区间删掉j个且第i个必取能覆盖的最大面积。 dp[i][j]=max(dp[i][j],dp[p][j-(i-p-1)]+calc(p,i))//calc(p,i)表示将第i个区间加到第p个区间后时新增的覆盖面积,因为i-p-1显然需要小于等于k，所以时间复杂度是O(n*k*k)，需优化。 之前的区间分为是否与当前区间有重叠部分这样两种。可以发现如果之前的一个dp[x][y]可以更新dp[i][j]，那么x-y=i-j-1; 所以我们可以开k个单调队列，如果队头的元素已经和当前第i个区间不重叠，就更新不重叠的答案，并弹出队头。 操作完成后，用队头及有重叠部分的区间来更新答案。 将dp[i][j]-a[i].r（为什么是这个值）放入第i-j个单调队列，进行更新。 具体的程序中写。 ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<queue> #define maxn 100009 using namespace std; int n,k,p[maxn],dp[maxn][109]; struct ding{ int l,r; }a[maxn],b[maxn]; struct ding2{ int node,val; }; deque<ding2>q[maxn]; bool cmp(ding t1,ding t2) {return t1.l==t2.l?t1.r>t2.r:t1.l<t2.l;} int main() { freopen("std.in","r",stdin); freopen("std.out","w",stdout); scanf("%d%d",&n,&k); b[0]=(ding){0,0}; for (int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r); if (k>=n) { printf("0\n"); return 0; } sort(a+1,a+1+n,cmp); int maxx=-1,cnt=0; for (int i=1;i<=n;i++) { if (a[i].r>maxx) b[++cnt]=a[i]; //去掉被包含区间 else k--; maxx=max(maxx,a[i].r); } if (k<0) k=0; n=cnt; for (int i=1;i<=n;i++) { for (int j=0;j<min(k+1,i);j++) { int now=i-j-1; while ((!q[now].empty())&&(b[q[now].front().node].r<b[i].l)) //如果当前队头的区间和第i个区间不重叠那就弹出 { ding2 to=q[now].front(); p[now]=max(p[now],to.val+b[to.node].r); //因为如果有重叠，那么dp[i][j]=dp[x][y]+a[i].r-a[x].r，所以放入队列的元素为dp[x][y]-a[x].r,我们用它来更新不重叠的答案 q[now].pop_front(); } dp[i][j]=max(dp[i][j],p[now]+b[i].r-b[i].l); //不重叠区间更新 if (!q[now].empty()) dp[i][j]=max(dp[i][j],q[now].front().val+b[i].r); //重叠的区间更新 int nowv=dp[i][j]-b[i].r; now=i-j; while ((!q[now].empty())&&(q[now].back().val<nowv)) q[now].pop_back(); q[now].push_back((ding2){i,nowv}); //放入队列 } } int ans=0; for (int i=1;i<=n;i++) for (int j=0;j<min(i,k+1);j++) if (j+n-i==k) ans=max(ans,dp[i][j]); //枚举哪个区间是最后一个被取的 printf("%d\n",ans); return 0; } ```