#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
 
int read() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}
 
#define maxn 100010
 
int f[maxn][10], val[maxn], A[maxn], cnt;
 
void up(int& a, int b) {
    a = max(a, b);
    return ;
}
 
int main() {
    int n = read(), m = read();
    while(m--) {
        int l = read(), r = read();
        val[l]++; val[r]--;
    }
    
    int tag = 0; cnt = 1;
    for(int i = 1; i <= n; i++) {
        tag += val[i];
        A[cnt]++;
        if(!tag) cnt++;
    }
    cnt--;
    memset(f, -1, sizeof(f));
    f[0][0] = 0;
    for(int i = 0; i < cnt; i++)
        for(int j = 0; j < 6; j++) if(f[i][j] >= 0) {
            up(f[i+1][(j+A[i+1])%6], f[i][j]);
            if(j < 3) up(f[i+1][A[i+1]%6], f[i][j] + 1);
        }
    
    int ans = -1;
    for(int i = 0; i < 3; i++) up(ans, f[cnt][i]);
    printf("%d\n", ans);
    
    return 0;
}

matrix67的题解帮助我一遍AC……内容如下：

把课程分成不同的三科完全是一种干扰。事实上，我们可以把这三科合成一科来做。试想，对于下面的数据

Politics:1-5

History:3-9

Geography:7-14

和数据

Politics:1-14

有什么不同？本质上看是没有区别的。我们完全可以把它们合并起来。我们并不关心哪一科的连续章数是多少，只关心某一章和紧接它后面的那一章之间是否有连续性。我们用数组Cont[i ]表示第i章和第i+1章是否不能分开（Cont意即使Continuity）。初始时Cont数组值全部为False（全部可以分开）。当读到两个数x和y时，对所有满足x

Accepted 有效得分：100 有效耗时：0ms

还是不太理解

感谢oimaster的题解

感谢oimaster的题解

通过 　　222人

提交 　　975次

35/100(35%) 祝贺自己提交一百了！

不看题解还真想不出来！惭愧。。

囧！我好像用了(N^2)的算法，再加了更新每个F[i]值数目的小剪枝，然后就过了...

郁闷......上一阶段影响这些这一阶段需要+1的最优解候选是保存在f,f,f里的，要小心不要搞错了......

排序

然后

j:=0;

for i:=1 to m do

if a>b[j] then begin

k:=b[j]+1;

while kb[j] then b[j]:=a;

k:=b[j]+1;

while kf then f:=f;

k:=(k+1) mod 6;

if f>f then f:=f;

inc(f);

for k:=2 to 6 do f[i,k mod 6]:=f[i-1,((b-b[i]+k) mod 6+6) mod 6];

end;

ans:=f[j,1]-1;

if ans

三科可以合成一科是显然的

当I可以与I-1分不同阶段时，最好分开，因为这样可以多一个阶段。

所以F：=MAX（F，F，F）+1；

这个方程就是这么来的

感觉离我这楼最近的那位牛的DP有点问题 ，yby。barty的DP应该是对了，但不知道怎么求解

膜拜提交14次那位

我是这样做的:

先找规律，再dp。

先写个枚举，发现满足条件的数 mod 6得数都为0－2之间。

f表示处理第i章,且该章在该部分的第k课时, j= k mod 6

则f= f[i-1,(j+5) mod 6] (j1 或 i-1与i不在同一阶段)

max{f+1,f[i-1,(j+5) mod 6]} (k=0,1,2 | j=1 , 且i-1与i在同一个阶段)

结果...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 25ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：66ms

我的方法是以连续块为阶段的。

先用o(nlogn)预处理出来k个连续块。然后o(k^2)的dp.

70分。利用了m67牛的疏忽。这样竟然能70。

在oibh上下了数据才发现。k最大才到了16000多。orz..

看看题解，继续弄。。。。

膜拜楼下的楼下的楼下的楼下的楼下

对于楼下的楼下的楼下的楼下，只有膜拜。。。

膜拜楼下的楼下的楼下！

膜拜楼下的楼下！

向qword的解法表示敬意

鄙人不习惯向i+1dp。

我提交了14次……

9次为普通方法加优化：时间复杂度较高、粗心（最高过8组）

4次为所提供方法：1次预处理少语句，1次3数最值函数错误，2次为提交失误