信息学湖南tim烦恼解题报告

1、Tim 烦恼解题【题目分析】取出题目中的要点，便可知道， 本题所要求的是在一个矩阵中，求若干个子矩阵，使它们符合题目的要求（即不相邻，也不最大。显然，本题是一个组合最优化问题。），并且使他们的分值和经过尝试会发现，由于本题数据量很大，搜索恐怕在很多反例，所以只得另外寻找其他的方法。为力；贪心法也存通常，在求解组合最优化问题中，采用动态规划法是一个不错的选择，那么本题是否可以采用动态规划来求解呢？是肯定的。【算法设计】为了研究的方便，可以将选择蛋糕块看成是对大矩阵的局部覆盖。设 C 为原来的分数矩阵，C(I,j)即便是第 I 行第j 列的蛋糕块的分数。设 A 为覆盖情况的矩阵，A(I,j)的值为

2、 0 或 1，为 0 则表示没有被覆盖，为 1 则表示被覆盖。研究一些简单情况可以发现，第 I 行的覆盖状态只受第 I-1 行的覆盖状态的影响。例如，A(2)=(0,1,0,1),则A(3)=(0,0,0,0),或(0,0,0,1),或(0,0,1,0),或(0,1,0,0),或(0,1,0,1),或(1,0,0,0),或(1,0,0,1),或(1,0,1,0)。即 A(3)的状态只与 A(2)的状态有关，而与 A(1)的状态无关。(注：以上 A(3)的状态是根据题目中的要求求得的)。有了这一点作为基础，动态规划的算法遍比较容易设计了。记 F(I,s)表示第 I 行状态为s 的覆盖情况的最优值

3、，其中 s 为 A(I)的所有状态中的一种。于是有动态规划方程：F(I,s)=MaxF(I-1,s)+c(s)(s 和s符合题设要求)上式中的 c(s)表示第 I 行覆盖状态为s 得分数和。【编程实现】在方程中，s 为一个 01 序列，而在具体实现时，可将其化成对应的十进制数。由于题设中 m= l then beginlinek := 1;dec(j, l);inc(v, valuei, k); endelse linek := 0; end;end;procedure search(dep, sum, k:eger);搜索与当前状态相符合的上一个状态 vartmp:eger; beginif

4、 dep m then beginif lastsum max then max := lastsum; exit;end;tmp := if tmp(kk=+ linedep - 1 + linedep; 2 then0) and (linedep - 1 = 1) and (linedep = 1) or(k = 1) and (k = 1) and search(dep +else(linedep - 1 = 0) and (linedep = 1) or (linedep - 1 = 1) and (linedep = 0)1, sum, 0)if tmp = 3 then(k = 1

5、) and (linedep - 1 = 1) and (linedep = 1)search(dep elsebeginsearch(dep search(depend;end;+1,sum + 1 shl (dep - 1), 1)+1,1,sum, 0);sum + 1 shl (dep - 1), 1)procedure main;主过程，动态规划递推求解 vari, j, all, temp:eger;beginall := 1 shl m fillchar(last, fillchar(line,ans := 0;- 1;sizeof(last), 0);sizeof(line), 0);for i := 1 beginfor j := beginget(i,max :=to n do0 to all doj, temp);low(eger);search(1, 0, 0); inc(max, temp);if max ans then ans := max; nowj := max;end;last := now; end;end;procedure show;输出结果 beginassign(output, ofn); rewrite(output);wrin(ans);close(output);end;v