暂无

无

无

本周摸了，由于假期小作业（由于我写得太慢

无

无

一道简单的dp题。

洛谷P1005:矩阵取数游戏

dp，高精度

在一个矩阵中取数，每次在n行中各取一个，只能取行首或者行尾。每次取数的得分为“取的数值*2^i”（i为第i次取数）。求一个取数方案使得得分之和最大。

由题意可知每行的取数是独立的，即我们只要分别处理每行的取数操作。
显然每次取数操作之间有先后关联，而取一次数的得分与其先前的所有操作密切相关，因此自然得出是dp。
令f(i,j)表示一行还剩第i至第j个数时得分的最大值，它的前状态为f(i-1,j)与f(i,j+1)，于是可以得到状态转移方程：
f(i,j)=max{f[i-1,j]+a[i-1]*2^(m-j+i-1),f[i,j+1]+a[j+1]*2^(m-j+i-1)}
由于答案没有取模，需要再用到高精度。

挺基础的_(:з」∠)_

无