Problem′s Website
Solution
这道题可以用记忆化搜索,比较好理解,于是我就不说了。。。
我们来说一下dp的做法。
很明确,我们可以将每一行分开处理,而且处理的点只带两端,明显的区间dp。
我们设f[i][j]为当前区间变为i, j时的最大得分。
每次取数时,至于i − 1和j + 1有关,次数我们可以推出来为m−j+i−1
状态转移方程还是比较好推的。
对于每一行
for i 1−m
for j m−i
f[i][j] =max(f[i−1][j]+a[i−1][j]×2n−j+i−1,f[i][j+1]+a[i][j+1]×2n−j+i−1);
最后只剩下一个数时
f[i][i]=max(f[i][i]+a[i][i]×2m);
对于每一行的f[i][i]取max,最后答案为n∑i=1maxmj=1(f[j][j]+a[j][j]×2m)
最后,温馨提示:本题要用高精度
Code
1 |
|
rp++
Related Issues not found
Please contact @dyrisingsunlight to initialize the comment