牛客—— 矩阵取数游戏 （DP+int128的黑科技）
矩阵取数游戏
https://ac.nowcoder.com/acm/problem/16645
牛客—— 矩阵取数游戏 （DP+int128的黑科技）
题意：
给定一个n*m的矩阵，矩阵中的每个元素都有自己的值a[i] [j] ，对于每一行，每次都可以取走该行的行首或行尾的元素，其对得分的贡献是 被取走的元素值 *2^i，其中i表示第i次取数（从1开始编号）,求取完n行的最大得分。
思路：
首先要考虑的是，对于每一行而言，每次的取数方案对答案的影响都只会本行，而不会影响到其他行，也就是说，我们可以单独对每一行进行考虑。
接下来单独考虑每一行，因为题目中要求取数只能从行首或是行尾取，所以会发现某一行的状态是从一个区间转变成了另一个区间，这恰好符合区间DP的特点： 以区间作为“阶段”，以划分区间的方法作为“决策” 。
我们假设dp[l] [r] 表示 取区间[ l , r ] 的最大值，定义a[l]表示该行的第l个数。根据题意取数只能从行首或行尾取，就说明此状态可以由[l+1,r]或[l,r-1]转移而来（取数的过程看做是向外扩展的过程）
dp[l][r]=max(dp[l+1][r]+a[l]*pow(2,q),dp[l][r-1]+a[l]*pow(2,q));///q表示是第q次取这个数
然后发现只能过60，又是一个跟 凸多边形的划分 一样的题目。
这次顺便学了一手int128的黑科技，板子
代码：
代码借鉴了参考博客里的写法，省去了快速幂的环节。
参考博客： https://www.luogu.com.cn/blog/JustinRochester/solution-p1005
查看24道真题和解析