老爷机(DP)

老爷机
Problem:I
Time Limit:1000ms
Memory Limit:65535K
Description
这一天，无所事事的Carmen意外地得到了一台老爷机。老爷机上有许多游戏，Carmen可以随意玩耍，但是每一个游戏都有固定的开始和结束时间。Carmen不想做一个中途挂机的坏孩子，所以每一个游戏一旦开始玩就必须玩到结束，不能中途停止去玩其他游戏，也不能从中途开始玩某一个游戏哦。这些游戏的开始时间可能会彼此重复，所以Carmen可以在其中任意选择，但是Carmen太贪玩了，如果Carmen在某一个时刻只有一个游戏可以玩，那么他一定会去玩。

我们假设这台老爷机上每天游戏的时间分布是固定的，而Carmen每天可以在两种游戏策略里面任意选择

第一种是Carmen在限定时间内游玩最长时间的游戏

第二种是Carmen在限定时间内游玩最短时间的游戏

因为这台机器实在是太老太破旧了，以至于Carmen如果当天选择了第一种游玩策略那么第二天他将只能选择第二种游玩策略

规定一个星期有7天

可怜的老爷机啊，请你宣判他一周只能休息多久呢。

（贪玩的Carmen会抓住一切玩的机会哦）
Input
第一行一个整数n表示每天的游玩时间，一个整数k，表示这台老爷机上共有k款游戏

接下来k行，一行两个整数l和r分别表示当前这款游戏的开始和结束时间

数据约定：

对100%的数据有1=<n<=1e5，1<=k<=1e5，保证所有输入数据合法即1<=l<r<=n+1
Output
一个整数代表老爷机一个星期内所能休息的时间
Sample Input
15 6
1 3
1 7
4 15
8 13
8 9
11 16
Sample Output
20
Hint

样例解释：如图可以做出时间分布图。在1时刻我们可以选择f或者g。
如果选择f，那么到4时刻的时候会一定选择h，直至终点都无法再玩其他游戏，总游戏时间为2+11=13
如果选择g，那么到8时刻的时候可以选择i或j
如果选择i，那么到11时刻的时候一定会选择k，直至终点都无法再玩其他游戏总游戏时间为6+1+5=12
如果选择j，直至终点都无法再玩其他游戏，那么总游戏时间为6+5=11
以上我们可以得到样例中每天的最长游戏时间为13，最短游戏时间为11。那么显然老爷机只能休息(15-13)×4+(15-11)×3=20
Tips:
请结合样例解释注意时间的含义（时段与时刻的区别）

![在这里插入图片描述](https://img-blog.csdnimg.cn/20200504105856138.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L

//线性dp，最后整合答案输出即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    int l;
    int r;
};
node in[100005];
int cnt[100005];
int dp1[100005]; //老爷机最多休息
int dp2[100005]; //老爷机最少休息
bool comp(node m, node n)
{
    if (m.l != n.l)
    {
        return m.l > n.l;
    }
    else
    {
        return m.r > n.r;
    }
}
int main()
{
    // freopen("7.in", "r", stdin);
    // freopen("7.out", "w", stdout);
    memset(dp1, 0, sizeof(dp1));
    memset(dp2, 0, sizeof(dp2));
    int t, n;
    cin >> t >> n;
    dp1[0] = 0;
    dp2[0] = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> in[i].l >> in[i].r;
        cnt[in[i].l]++; //记录开始时间
    }
    sort(in, in + n, comp); //优先按照开始时间从大到小排序
    int p = 0;
    for (int i = t; i >= 1; i--)
    {
        if (cnt[i] == 0) //空闲
        {
            dp1[i] = dp1[i + 1] + 1;
            dp2[i] = dp2[i + 1] + 1;
        }
        else
        {
            dp1[i] = dp1[in[p].r]; //一定要取，那就给取上，如果没有这一步就有可能出现一个也不取的情况
            dp2[i] = dp2[in[p++].r];
            for (int j = 1; j < cnt[i]; j++)
            {
                dp1[i] = max(dp1[i], dp1[in[p].r]);
                dp2[i] = min(dp2[i], dp2[in[p++].r]);
            }
        }
    }
    cout << 4 * dp2[1] + 3 * dp1[1] << endl; //输出即可
    return 0;
}