信息学集训队作业0071-number

题目0071–Number（奶牛编号）题目来源：Romania推荐者：许智磊英文原文二、中文翻译奶牛编号(number.pas|cpp|exe)【问题描述】FarmerJohn的农场里居住着N头奶牛，为了方便管理，FarmerJohn希望用1到N数字对这N头奶牛进行编号。然而，奶牛们早已经厌倦了从1到N按顺序简单的编号。奶牛Bessy提出这样一种编号规则：按顺序第i个奶牛的编号应当小于第i+2和第i+3个奶牛的编号（如果存在的话）。当然，这种编号方式可能使不同的奶牛有相同的编号。不过FarmerJohn还是很乐意尝试这种新颖的编号方式。同时，他对一共有多少编号方案产生了兴趣。不过这个方案数可能太大了，而FarmerJohn对大数字的运算显然力不从心，于是，他就来求助身为高级程序设计员的你。你能帮助FarmerJohn计算出一共有多少编号方案么？注意了，FarmerJohn一看到大数字就会头昏，所以你只要提供答案的最后5位^_^【输入文件】输入文件名：number.in输入文件有一行一个整数N（1<N<200），表示奶牛的个数。【输出文件】输出文件名：number.out输出文件有一行，为答案的最后5位。【样例输入一】2【样例输出一】00004【样例说明一】上例中，编号方案为：(1,1),(1,2),(2,1),(2,2)。【样例输入二】3【样例输出二】00009【样例说明二】上例中，编号方案为：(1,1,2),(1,1,3),(1,2,2),(1,2,3),(1,3,2),(1,3,3),(2,1,3),(2,2,3),(2,3,3)。三、初步讨论情况姜尚仆递推陆可昱递推邵煊程显然可以递推解决。周源我的算法和xzl一样。不会更好的方法了。雷环中我也只想到了O(N^4)的算法，更好的算法还需要更深入的想一想。方奇曾经想过一个O(n^2)的算法，后来发现是错的。暂时只知道O(n^4)的动态规划。张云亮这样的做法是对的，但是只要把其中的条件改一改，Max(A,B)<=y,C<=z在加上算好Max(A,B)<=y,C=z的情况a后S(len,y,z):=(情况a的方法)+S(len,y,z-1)这样就可以起到降次的作用了。王知昆设状态f[i,j]表示前n位中第1位和第2位均大于x。那么f[i,j]=f[i,j+1]+Σf[i-2,a1+1](a1=j,j+1,……,n)+f[i-1,j+1]时间复杂度是O(N2)，伍昱递推设f[I,j]表示前I个数，最大的不超过j的方案数，可以得到：求的就是f[n,n]那个∑的值可以随j的循环累加算得因此时间复杂度为O(n2)张云亮这样的做法是对的，但是只要把其中的条件改一改，Max(A,B)<=y,C<=z在加上算好Max(A,B)<=y,C=z的情况a后S(len,y,z):=(情况a的方法)+S(len,y,z-1)这样就可以起到降次的作用了。项荣璟按常规的思路提出O(n^4)的递推，从另一个角度能提出O(n^3)的递推，用普通的优化递推的方法将复杂度降到了O(n^2)。呵呵饶向荣可以优化为O(N3)。可以写出一般的动态规划方程：表示后个最小编号为j，而第后I个编号为I的方案总数。其中的可以用数组表示。而每个阶段计算的复杂度并不高，只要在算时，附带的计算就可以了，而状态方程中的可以在动态规划时累加就可以了。所以总的状态方程可以变为：f[len,i,j]=Tf[len,j]+sum所以总的时间复杂度为O(N3),空间复杂度为O(N2)。此外还有将状态方程改变一下就可以将为O(N2)。何林同学有介绍，这里不说了。金恺O(N3)的动态规划，设fi,j,k表示给第i到第N头奶牛编号，其中第i+1头奶牛的编号为j，第i+2~N头奶牛的最小编号为k，这样的方案数有多少。状态转移方程如下：，表面上看来复杂度是O(N4)，但实际上可以降为O(N3)：因为当i,k确定了就可计算出方程的第一部分，当j<k时就给fi,j,k加上Part1。方程第二部分的计算可以让j从大到小循环，用辅助变量temp存下当前的取值，然后当j>k时，令temptemp+fi+1,k,j。伪代码如下：循环in–3到1循环k1到nPart10;temp0;循环jk到ndoPart1Part1+fi+1,j,k;循环jn到1如果k>j那么fi,j,kPart1+temp否则fi,j,ktemp如果j>k那么temptemp+fi+1,k,j用滚动数组后空间只需要O(N2)。我的程序N=200时只需要0.66s（测试环境：P41.7GB，Window2002，TP7.0）林希德何林同学说有O(n2)的算法，很精彩，以至于我羞于述说我的O(n3)的破DP——动态规划状态分离：Gi,x,y,z表示给前i头奶牛编号，其中第i-2头编号为x，第i-1头编号为y，第i头编号为z时的编号方案总数（当然只保存整数的最后5位）。状态转移：Gi,x,y,z=。复杂度分析。先撇开存储量不谈，单时间复杂度就高达O(n5)，无法忍受。那么，能否进行优化呢？优化方案1：状态降维如果Ri表示第头奶牛的编号，那么可得不等关系如下：Ri+1>Ri-1,Ri-2Ri-1>Ri-3，Ri-4Ri-2>Ri-4，Ri-5Ri-3>Ri-5,Ri-6……可见，不等关系式覆盖了从1i-1的所有奶牛编号，不等关系传递的结果是：Ri+1应当大于每一个Rj（0<j<i）。因此，状态分离中的x,y可以合并成一维。重新进行状态分离：Gi,u,v表示给前i头奶牛编号，其中第i头奶牛编号为u，第Max{R1Ri-1}=v的编号方案总数。状态转移：优化方案2：减少转移路径数这个，我反正是想不出什么优化。优化方案3：减少转移费用计算函数Si-1,v复杂度=O(状态数)*O(转移路径)*O(转移费用)=O(n2)*O(n)*O(1)=O(n3)计算函数Ti-1,v,u函数T的状态转移方程如下：Ti-1,v,u=Ti-1,v,u-1+Gi-1,v,u-1所以，计算所有T函数的复杂度为=O(状态数)*O(转移路径)*O(转移费用)=O(n3)*O(1)*O(1)=O(n3)综上，动态规划的总复杂度为O(n3)，空间也是O(n3)的。许智磊令f(len,min)代表长度为len，每个数都不小于min的合法标号序列的个数，那么讨论各种情况（何林的解题报告中有）可以得到f(h,min)=f(h,min+1)+f(h-1,min+1)+。设s(h,min)=，则：（以上引用自何林的报告）。何林问题抽象若数列{ai|1≤i≤n,1≤ai≤n}满足：对于任意的1≤i≤n-2，有ai<ai+2对于任意的1≤i≤n-3，有ai<ai+3则称此数列为“合法数列”。求合法数列的总数。状态描述设f(h,min)表示这样的数列的总数：数列长度为h。令数列的元素为a1,a2,…,ah。a1,a2≥min对于任意的1≤i≤h-2，有ai<ai+2对于任意的1≤i≤h-3，有ai<ai+3分三类讨论：（这里假设n足够大）第一类：a1,a2≥min+1。这时的总数是f(h,min+1)第二类：a2=min,a1≥min。可以把a3,a4,…,ah看作一个长度为h-2的新数列。必须满足：a3,a4>a1a4,a5>a2对于任意的3≤i≤h-2，有ai<ai+2对于任意的3≤i≤h-3，有ai<ai+3根据(1)、(3)和(4)可以得到：a5>a3>a1≥a2a4>a1≥a2因此(2)可以根据(1),(3),(5)推得。故而可以化简为：a3,a4>a1对于任意的3≤i≤h-2，有ai<ai+2对于任意的3≤i≤h-3，有ai<ai+3这样的数列有f(h-2,a1+1)个。因此第二类情况中共有个符合f(h,min)定义的数列。第三类：a2>min，a1=min。必有a2>a1。将a2,a3,…,ah看作一个长度为h-1的数列。必须满足：a2,a3,a4>a1对于任意的2≤i≤h-2，有ai<ai+2对于任意的2≤i≤h-3，有ai<ai+3根据(2),(3)有：a4>a2>a1于是(1)可化简为：a2,a3>a1，综合起来就是：a2,a3>a1对于任意的2≤i≤h-2，有ai<ai+2对于任意的2≤i≤h-3，有ai