[洛谷P1005][区间DP/高精度]

原题链接：P1005 [NOIP2007 提高组] 矩阵取数游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

摘要

        有一n*m的矩阵，对于第i行，每次取走一个端点值a，同时此行分数增加a*(2^k)，k代表第k次取数。求n行最大得分总和。

分析

       1. 容易得知，每一行得分都是独立的，不会影响其他行，因此只要确保每行自己得分最大，则总和得分便是最大[最优子结构]。同时由于每行得分独立计算，因此我们可以每读取一行时就直接进行计算，可以减少时间空间复杂度(虽然没什么用就是了= =)

        2.数据范围小于等于80，2^80远超longlong，所以需要高精。

流程

        运用区间DP思想，用 F[i][j] 表示区间 [i, j] 可获得的最大分数。

        进行状态转移时，转移到区间 [i, j] 的上一区间必定是 [i-1, j] 或者 [i, j+1]。同时获得分数a*(2^k)，且 k=m-(j-i+1)，因此我们很容易得到状态转移方程：

F[i][j] = max(F[i][j + 1] + 2^(m - j + i - 1) * arr[j + 1], 

                     F[i - 1][j] + 2^(m - j + i - 1) * arr[i - 1]); 

代码实现

        首先关于高精度，先分享一下网上抄的高精模板：

        但一般没啥用...而且效率太低，虽然也能过。但我们有更简单的方法。

        那就是：__int128！！！

        note：__int128仅64位GCCG++支持，不在C++标准中！不在namespace std中！但64位GCC可直接使用[如果你本地编译器无法使用，可以使用洛谷在线IDE测试](洛谷在线 IDE (luogu.com.cn))

        顾名思义，__int128就是占用128字节的整数存储类型，由于是二进制，所以范围是 -2^127~2^127-1，如果使用 unsigned __int128，则范围变成 0^128，即约39位整数！足以满足本体要求。

        但关于其具体使用方法本问不再过多介绍。

        关键代码：

        最终代码（粘板子特供）：

        （我是不是写的有点烂啊，不知道说得清不清楚= =但绝对不是我懒！哼！）