背景:
更新了题解的青藤OJ真的太香了,让人情不自禁想要写一篇
————————————————————————————————————————————
题目思路:
类似于最长上升子序列问题
一段区间有两个选择:
①独立成段
②接在别人后面
那我们只需要排序之后在按最长上升子序列处理即可。
————————————————————————————————————————————
下面奉上AC代码:
鸡汤来嘞~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include<bits/stdc++.h>
#define int long long
using namespace std;
const long long maxn=2e3+500+10;
struct node{
int s,e;
}a[maxn];
bool cmp(node x,node y){//排序
if(x.s != y.s)return x.s < y.s;
return x.e < y.e;
}
int n;
int dp[maxn];
signed main(){
cin>>n;
for(int i=1;i<=n;i++){//读入数据不多说了
cin>>a[i].s>>a[i].e;
}
sort(a+1,a+n+1,cmp);//结构体排序
for(int i=1;i<=n;i++){//枚举当前第i个申请
dp[i]=a[i].e - a[i].s;//至少时长为独立成段的时长,即:结束时间-开始时间
for(int j=1;j<i;j++){
if(a[i].s >= a[j].e ){//判断是否有资格接上
dp[i]=max(dp[i],dp[j]+(a[i].e-a[i].s));//状态转移方程
}
}
}
int ans=INT_MIN;
for(int i=1;i<=n;i++){
ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}