摸鱼

视频题解点击此处查看

题目阅读

AC狗在家上网课，狗星教育局对于线上课没有经验，导致了AC狗有了摸鱼机会，现在给你AC狗的上课时间 T分钟， 从1分钟到T分钟结束，AC狗只能在每堂课开始进入课堂，并且要完整上完这堂课，如果当前没在上课并且其他课程开始了，那么ac狗就要选择一堂课去上。现在让你帮他计算最多能摸鱼多久？

题意抽象

给定一个最大值T，和N个区间，区间的范围一定在1~T内，同时如果选择了一个区间进入后就不用选择其他有冲突的区间（指区间发生交叉），问你有没有一种方法可以使区间覆盖的区域最小。

算法分析

本题我们可以采用线性DP + 二分 + 递归的做法来实现。

​ 根据t和n输入数据后，我们通过起点A与时长W分钟推算出下课时间，同时记录下时间为A时开课的数量，以起点A开始的课程数+1，之后进入递归查找最优解。 通过二分函数查找大于等于坐标now的课程下标，如果已经为最后一节课则直接返回dp[now] = t - now + 1 。 取出该课程的起点，遍历以该课程为起点开始的所有的结束课程时间，查找两者之间跨度最大的课程即可。

代码讲解

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PII pair<int,int>
const int N=1e6+10;
int dp[N];
PII a[N];
vector<int>v[N];
map<int,int>mp;
int t,n;
int dfs(int now)
{
    if(dp[now]) return dp[now];
    auto it=mp.lower_bound(now);
    if(it==mp.end())
    {
        return dp[now]=t-now+1;
    }
    int x=it->first;
    for(int i=0;i<v[x].size();i++)
    {
        dp[now]= max(dp[now], dfs(v[x][i])+x-now);
    }
    return dp[now];
}
void solve()
{
    cin>>t>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].first>>a[i].second;
        v[a[i].first].emplace_back(a[i].first+a[i].second);
        mp[a[i].first]++;
    }
    cout<<dfs(1)<<endl;
}
int main()
{
    IOS
    solve();
    return 0;
}