DP——Luogu2439 [SDOI2005]阶梯教室设备利用

阶梯教室设备利用"/>

DP——Luogu2439 [SDOI2005]阶梯教室设备利用

传送门
我们先按结束时间从小到大把演讲排序，然后考虑dp
f[i]表示1~i时间能够利用的最长时间
状态转移方程：f[i]=max(f[i-1],f[a[j].begin-1]+a[j].end-a[j].begin+1)
其中j表示结束时间是i的演讲
最后答案是f[a[最后一个].end]
0msAC

#include<bits/stdc++.h>
using namespace std;
struct ppap{int x,y;}a[100001];
int f[100001];
inline bool cmp(ppap a,ppap b){return a.y<b.y;}
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);sort(a+1,a+n+1,cmp);int k=1;for(int i=1;i<=a[n].y;i++){f[i]=f[i-1];for(;a[k].y<=i&&k<=n;k++)f[i]=max(f[i],f[a[k].x]-1+a[k].y-a[k].x+1);}printf("%d",f[a[n].y]);return 0;
}