P2439 [SDOI2005]阶梯教室设备利用 And P1868 饥饿的奶牛 题解

题解"/>

P2439 [SDOI2005]阶梯教室设备利用 And P1868 饥饿的奶牛 题解

【题目链接】

P2439
P1868

【解题思路】

我们先来思考【P2493】，考虑用动态规划来做。

为了使动态规划没有后效性，我们需要先对演讲的时间按照一定的顺序来排序，这样我们就可以保证动态规划是单调递增的。

我们按照右端点从小到大排，到时后就可以找出一个第一个比左端点大的，就可以进行状态转移。

我们定义 d i d_i di​ 为排序后前 i i i 个演讲的最长时间，则 d i = d_i= di​= 不选当前演讲即 d i − 1 d_{i-1} di−1​，以及在前面选一个结束时间可以接上当前开始时间的数中的最大值。

动态转移方程
d i = max ⁡ ( max ⁡ j = 1 i − 1 { d j + t 2 i − t 1 i } , d i − 1 ) d_{i}=\max(\max\limits{_{j=1}^{i-1}}\{d_{j}+t2_i-t1_i\},d_{i-1}) di​=max(maxj=1i−1​{dj​+t2i​−t1i​},di−1​)
但是我们发现这样子做的话时间复杂度是 O ( n 2 ) O(n^2) O(n2) 是过不了【P1868】的，我们可以给它加一点小优化，使用二分查找，因为数组是单调递增的所以可以二分，把时间复杂度降为 O ( n l o g n ) O(nlogn) O(nlogn) 后我们就能愉快的AC了。

注意：
【P1868】 t 2 i − t 1 i t2_i-t1_i t2i​−t1i​ 还要加上多减的一，并且左右端点不能重复。
【P2439】 O ( n 2 ) O(n^2) O(n2) 做法循环要从0开始，因为可以不选。

【CODE】

【P2439】 O ( n 2 ) O(n^2) O(n2) 做法

#include<iostream>
#include<algorithm>
using namespace std;
int n,maxn;
struct NOTE
{int x;int y;}t[31000];
int f[31000];
bool cmp(NOTE a,NOTE b)//保证答案的单调性
{return a.y<b.y;
}
int main()
{cin>>n;for (int i=1;i<=n;i++)scanf("%d%d",&t[i].x,&t[i].y);sort(t+1,t+n+1,cmp);for (int i=1;i<=n;i++){f[i]=t[i].y-t[i].x;//如果自己是最大的for (int j=0;j<i;j++)//注意是从0开始，可以不选{if (t[i].x>=t[j].y)//当可以接上f[i]=max(f[i-1],f[j]+t[i].y-t[i].x);//比较取和不取}}cout<<f[n];return 0;
}

【P2439】 O ( n l o g n ) O(nlogn) O(nlogn) 做法

#include<iostream>
#include<algorithm>
using namespace std;
int n,maxn,dd,flag;
struct NOTE
{int x;int y;}t[3100000];
int f[3100000];
int q[3100000];
bool cmp(NOTE a,NOTE b)
{return a.y<b.y;
}
int erfen(int l,int r,int x)
{flag=0;//返回0代表不选while (l<=r){int mid=l+(r-l)/2;//一个小细节防止爆intif (t[mid].y<=x){flag=mid;//保存答案l=mid+1;}else r=mid-1;}return flag;
}
int main()
{cin>>n;for (int i=1;i<=n;i++)scanf("%d%d",&t[i].x,&t[i].y);sort(t+1,t+n+1,cmp);for (int i=1;i<=n;i++){f[i]=max(f[i-1],f[erfen(1,i-1,t[i].x)]+t[i].y-t[i].x);	//因为答案是单调递增的，所以二分能保证最优}cout<<f[n];return 0;
}

【P1868】 O ( n l o g n ) O(nlogn) O(nlogn) 做法

#include<iostream>
#include<algorithm>
using namespace std;
int n,maxn,dd,flag;
struct NOTE
{int x;int y;}t[3100000];
int f[3100000];
int q[3100000];
bool cmp(NOTE a,NOTE b)
{return a.y<b.y;
}
int erfen(int l,int r,int x)
{flag=-1;while (l<=r){int mid=(l+r)/2;if (t[mid].y<x)//头尾不能重叠{flag=mid;l=mid+1;}else r=mid-1;}return flag;
}
int main()
{cin>>n;for (int i=1;i<=n;i++)scanf("%d%d",&t[i].x,&t[i].y);sort(t+1,t+n+1,cmp);for (int i=1;i<=n;i++){if (dd=erfen(1,i-1,t[i].x))f[i]=max(f[i-1],f[dd]+t[i].y-t[i].x+1);	//把头减掉了，要加回去maxn=max(f[i],maxn);}cout<<maxn;return 0;
}