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次为提交失误

这道题的关键有两点:

一是将三科合并为一科

二是发现函数f(k)=(3^k+5^k+2^k+4) mod 7的值每过6个就重复一次

然后存储状态为dp,i代表处理第i章,j代表当前k除6的余数.

dp=dp (i-1与i必须在同一阶段)

=max{dp,dp,dp}+1 (i-1与i不必同一阶段)

剩下的情况估计都会吧 O(N)搞定