牛客—— 矩阵取数游戏（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的黑科技，板子

代码借鉴了参考博客里的写法，省去了快速幂的环节。