由于对matrix67牛的热爱我耐心地搞掉了此题= =。。。
http://www.vijos.cn/Problem_Show.asp?id=1246
先扔官方题解
把课程分成不同的三科完全是一种干扰。事实上，我们可以把这三科合成一科来做。试想，对于下面的数据
Politics:1-5
History:3-9
Geography:7-14
和数据
Politics:1-14
有什么不同？本质上看是没有区别的。我们完全可以把它们合并起来。我们并不关心哪一科的连续章数是多少，只关心某一章和紧接它后面的那一章之间是否有连续性。我们用数组Cont[i ]表示第i章和第i+1章是否不能分开（Cont意即使Continuity）。初始时Cont数组值全部为False（全部可以分开）。当读到两个数x和y时，对所有满足x<=i
令满足条件(3^k+5^k+2^k+4) mod 7=0的所有k值为集合P。集合P可以预处理出来。问题就简化为：将1..n划分成最多的区间，使得每个区间的长度都属于P，且这些区间的结束点不能与后面有连续性。我们用f[i ]表示前i章可以划分出来的最多的区间数，则f[i ]=Max{ f[j-1]+1 (i-j+1∈P且Cont[j-1]=False) }。这是一个O(n^2)的动态规划，它可以通过一半的数据。为了将时间复杂度优化到O(n)，我们还需要继续观察。
函数f(k)=a^k mod m一定会在某个地方开始产生循环，因为函数的取值只能是小于m的非负整数，一旦这个值出现重复则必然循环。类似地，可以证明，函数f(k)=(3^k+5^k+2^k+4) mod 7的值每过6个就重复一次。一个数k属于P当且仅当k除以6余0、1或者2。于是，我们得到了线性的转移方程：设f[i,j]表示将前i章按这样的要求划分所能得到的最多阶段数：最后一部分的章节数除以6余j，且前面的章节按要求划分。因此，j的取值只能是0到5。于是，我们有：
f[i,1]┬ :=f[i-1,0] 当Cont[i-1]=True时；
└ :=Max{ f[i-1,0],f[i-1,1],f[i-1,2] }+1 当Cont[i-1]=False时；
f[i,2]:=f[i-1,1]；
f[i,3]:=f[i-1,2]；
f[i,4]:=f[i-1,3]；
f[i,5]:=f[i-1,4]；
f[i,0]:=f[i-1,5]；
最后输出f[n,0]、f[n,1]、f[n,2]中的最大值即可。
由于先前对Cont数组的预处理已经达到了O(n^2)，复杂度高于动态规划的转移，成为了算法效率的瓶颈。因此，我们需要用新的方法使得可以在O(n)的时间里判断某一章是否与后面有关联。我们用StartPos[i ]表示从i开始的连续章节有多少个，用EndPos[i ]表示以i结束的连续章节有多少个。也就是说，读入x和y时，StartPos[x]和EndPos[y]各增加1。在动态规划转移的过程中，我们不断更新一个变量t的值，每一次i增加时都让t:=t+StartPos[i ]-EndPos[i ]。t值实质上表示了包含第i章的连续章节有多少个。当t=0时，我们便可以确定此时的i不与后面连续。
自己当初想的时候想到了把所有科目区间合并
也想到了那个天数规律以6为周期的循环
不过智商太低没有想到那个动归状态表示法
刚看题解的时候那个f[i,j]所表达的意义我理解了半天
一直没有很清楚地想明白，导致了我后面DP初始化写错不停地WA
其实那个f[i,j]是状态压缩
原来的定义应该是g[i,j]
i表示取到第i章，j表示最后一个阶段包含几章
因为有那个mod 6的规律所以就可以用f[i,j]来表示所有g[i,j]的所有状态
那个g[i,j]的定义方法我根本没有想到 我不过往背包方面想了想= =
智商不够啊。。
当初我一直在想为什么状态转移的时候只在f[i,1]里面决定决策
还有为什么初始值应该赋成f[1,1]:=1
f[i,1]代表g[i,1],g[i,7],g[i,13]等状态的最优解
而f[i,j]状态是不管最后一个阶段是否可以与后面的章向关联的
如果第i-1章和第i章是可以分开的，那么一定可以从i-1和i之间分开
新分割出来的最后一个阶段只包含第i章这一个章
所以初始值为f[1,1]:=1也就可以理解了= =。。
又因为我们的决策只考虑第i-1章和第i章是否可以分，所以状态转移的决策只发生在g[i,1]
也就是f[i,1]里面，所以dp状态转移的方程也能够理解了
因为n是最后一个不需要考虑是否和后面的章节连续
所以最后只需要找最后一部分天数符合要求的情况
即输出max(f[n,0],f[n,1],f[n,2])
（以上的思考过程大牛觉得是显然的，而我想了好久，这就是智商差距啊
你不得不承认这种差距是后天很难弥补的）
还有那个StartPos和EndPos
其实那天刚写过一个类似的区间题p1238
lx刚告诉我这个方法 = =
我有想过用到这题不过当时没有想出题解的dp所以觉得没有什么用就没仔细想下去了
笨死了啊。。。
http://www.vijos.cn/Problem_Show.asp?id=1246
先扔官方题解
把课程分成不同的三科完全是一种干扰。事实上，我们可以把这三科合成一科来做。试想，对于下面的数据
Politics:1-5
History:3-9
Geography:7-14
和数据
Politics:1-14
有什么不同？本质上看是没有区别的。我们完全可以把它们合并起来。我们并不关心哪一科的连续章数是多少，只关心某一章和紧接它后面的那一章之间是否有连续性。我们用数组Cont[i ]表示第i章和第i+1章是否不能分开（Cont意即使Continuity）。初始时Cont数组值全部为False（全部可以分开）。当读到两个数x和y时，对所有满足x<=i
令满足条件(3^k+5^k+2^k+4) mod 7=0的所有k值为集合P。集合P可以预处理出来。问题就简化为：将1..n划分成最多的区间，使得每个区间的长度都属于P，且这些区间的结束点不能与后面有连续性。我们用f[i ]表示前i章可以划分出来的最多的区间数，则f[i ]=Max{ f[j-1]+1 (i-j+1∈P且Cont[j-1]=False) }。这是一个O(n^2)的动态规划，它可以通过一半的数据。为了将时间复杂度优化到O(n)，我们还需要继续观察。
函数f(k)=a^k mod m一定会在某个地方开始产生循环，因为函数的取值只能是小于m的非负整数，一旦这个值出现重复则必然循环。类似地，可以证明，函数f(k)=(3^k+5^k+2^k+4) mod 7的值每过6个就重复一次。一个数k属于P当且仅当k除以6余0、1或者2。于是，我们得到了线性的转移方程：设f[i,j]表示将前i章按这样的要求划分所能得到的最多阶段数：最后一部分的章节数除以6余j，且前面的章节按要求划分。因此，j的取值只能是0到5。于是，我们有：
f[i,1]┬ :=f[i-1,0] 当Cont[i-1]=True时；
└ :=Max{ f[i-1,0],f[i-1,1],f[i-1,2] }+1 当Cont[i-1]=False时；
f[i,2]:=f[i-1,1]；
f[i,3]:=f[i-1,2]；
f[i,4]:=f[i-1,3]；
f[i,5]:=f[i-1,4]；
f[i,0]:=f[i-1,5]；
最后输出f[n,0]、f[n,1]、f[n,2]中的最大值即可。
由于先前对Cont数组的预处理已经达到了O(n^2)，复杂度高于动态规划的转移，成为了算法效率的瓶颈。因此，我们需要用新的方法使得可以在O(n)的时间里判断某一章是否与后面有关联。我们用StartPos[i ]表示从i开始的连续章节有多少个，用EndPos[i ]表示以i结束的连续章节有多少个。也就是说，读入x和y时，StartPos[x]和EndPos[y]各增加1。在动态规划转移的过程中，我们不断更新一个变量t的值，每一次i增加时都让t:=t+StartPos[i ]-EndPos[i ]。t值实质上表示了包含第i章的连续章节有多少个。当t=0时，我们便可以确定此时的i不与后面连续。
自己当初想的时候想到了把所有科目区间合并
也想到了那个天数规律以6为周期的循环
不过智商太低没有想到那个动归状态表示法
刚看题解的时候那个f[i,j]所表达的意义我理解了半天
一直没有很清楚地想明白，导致了我后面DP初始化写错不停地WA
其实那个f[i,j]是状态压缩
原来的定义应该是g[i,j]
i表示取到第i章，j表示最后一个阶段包含几章
因为有那个mod 6的规律所以就可以用f[i,j]来表示所有g[i,j]的所有状态
那个g[i,j]的定义方法我根本没有想到 我不过往背包方面想了想= =
智商不够啊。。
当初我一直在想为什么状态转移的时候只在f[i,1]里面决定决策
还有为什么初始值应该赋成f[1,1]:=1
f[i,1]代表g[i,1],g[i,7],g[i,13]等状态的最优解
而f[i,j]状态是不管最后一个阶段是否可以与后面的章向关联的
如果第i-1章和第i章是可以分开的，那么一定可以从i-1和i之间分开
新分割出来的最后一个阶段只包含第i章这一个章
因为我们并不在乎最后一个阶段是否是完整的
所以决策里面的+1也就是指的这一个章（即使它不完整）所以初始值为f[1,1]:=1也就可以理解了= =。。
又因为我们的决策只考虑第i-1章和第i章是否可以分，所以状态转移的决策只发生在g[i,1]
也就是f[i,1]里面，所以dp状态转移的方程也能够理解了
因为n是最后一个不需要考虑是否和后面的章节连续
所以最后只需要找最后一部分天数符合要求的情况
即输出max(f[n,0],f[n,1],f[n,2])
（以上的思考过程大牛觉得是显然的，而我想了好久，这就是智商差距啊
你不得不承认这种差距是后天很难弥补的）
还有那个StartPos和EndPos
其实那天刚写过一个类似的区间题p1238
lx刚告诉我这个方法 = =
我有想过用到这题不过当时没有想出题解的dp所以觉得没有什么用就没仔细想下去了
笨死了啊。。。
没有评论:
发表评论