题解 P1005 【矩阵取数游戏】

JustinRochester · 2018-08-22 14:04:39 · 题解

几个月前本蒟蒻以为这题是个贪心，结果......可想而知

几个月后本蒟蒻发现它是个 区间dp 还想到了正解，结果楞是数组开小了一个单元，RE 了......

【分析】

其实虽然这题不是个贪心，但还是有一点贪心的思想

对于题目的描述，我可以看成有 n 个同学对每一行取数

且每行 m 个数中，得分的计算规则不变

那么，题目就是求这 n 个同学得分 ans_i 之和的最大值

由于每个同学的得分是相互独立的

所以，想要求得分最大值，就是对每个同学的得分最大值求和

即

--

那么，接下来

我们考虑如何将每个同学的得分最大

对于一个区间 [i,j] 的得分最大值，我们记为 dp_{i,j}

那么，由题目得每次取数都必须从区间的开头或者结尾取数

也就是说 dp_{i,j} 与 dp_{i,j-1} 、 dp_{i+1,j} 之间有着必然的联系，转移方程肯定从这里入手

假设与 dp_{i,j-1} 有关的状态更优。那么，我们先考虑 dp_{i,j} 与 dp_{i,j-1} 的关系

我们可以很清楚的知道，dp_{i,j} 是在区间 [i,j] 上取数的最大值，一共是 (j-i+1) 个数

而 dp_{i,j-1} 是在区间 [i,j-1] 上取数的最大值，一共是 (j-1-i-1)=(j-i-2) 个数

按照我们之前的假设，与 dp_{i,j-1} 的状态更优

那么，对于区间 [i,j] 的得分，显然是先取第 i 个数，再对后面的区间 [i,j-1] 取最大得分

那么，取第 i 个数的得分为 map_j \times 2^1

取后面的区间 [i,j-1] 的最大得分为 (\sum_{k=1}^{j-i+2} map_{c_k}\times 2^{k+1})_{max} ， 其中 c_k 是区间[i,j-1]中的数，且互不相同

根据定义，我们又可以知道 dp_{i,j-1}=(\sum_{k=1}^{j-i+2} map_{c_k}\times 2^k)_{max}

因此，联立上面式子，得出

如果 dp_{i,j-1} 的状态更优，那么 dp_{i,j}=dp_{i,j-1} \times 2 +map_j \times 2=2(dp_{i,j-1}+map_j)

同理，可以得出，如果 dp_{i+1,j} 的状态更优，那么，同样有 dp_{i,j}=2(dp_{i+1,j}+map_i)

因此，可以归纳出状态转移方程

--

你以为这就完了吗......

我们算一下答案的范围