【洛谷】【区间dp】【高精度】P1005 [NOIP2007 提高组] 矩阵取数游戏

题目链接：https://www.luogu.com.cn/problem/P1005

题目描述

  帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 n×m 的矩阵，矩阵中的每个元素 ai,j 均为非负整数。游戏规则如下：

1. 每次取数时须从每行各取走一个元素，共 n个。经过 m次后取完矩阵内所有元素；
2. 每次取走的各个元素只能是该元素所在行的行首或行尾；
3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 x2i，其中 i表示第 i次取数（从 1开始编号）；
4. 游戏结束总得分为 m次取数得分之和。

  帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

输入格式

  输入文件包括 n+1 行：

  第一行为两个用空格隔开的整数 n和 m。

  第 2~ n+1 行为n×m矩阵，其中每行有 m 个用单个空格隔开的非负整数。

输出格式

  输出文件仅包含 1行，为一个整数，即输入矩阵取数后的最大得分。

测试样例

输入
2 3
1 2 3
3 4 2

输出
82

解题思路

1.状态转移方程

  设f[l][l+len][i]为左端点为l，右端点为l+len,第i行取数所能获得的最大值，则状态转移方程如下 f [ l ] [ l + l e n ] [ i ] = m a x ( 2 ∗ f [ l + 1 ] [ l + l e n ] [ i ] + 2 ∗ a [ i ] [ l ] , 2 ∗ f [ l ] [ l + l e n − 1 ] [ i ] + 2 ∗ a [ i ] [ l + l e n ] ) f[l][l+len][i]=max(2*f[l+1][l+len][i]+2*a[i][l],2*f[l][l+len-1][i]+2*a[i][l+len]) f[l][l+len][i]=max(2∗f[l+1][l+len][i]+2∗a[i][l],2∗f[l][l+len−1][i]+2∗a[i][l+len])   可以化简为 f [ l ] [ l + l e n ] [ i ] = m a x ( f [ l + 1 ] [ l + l e n ] [ i ] + a [ i ] [ l ] , f [ l ] [ l + l e n − 1 ] [ i ] + a [ i ] [ l + l e n ] ) ∗ 2 f[l][l+len][i]=max(f[l+1][l+len][i]+a[i][l],f[l][l+len-1][i]+a[i][l+len])*2 f[l][l+len][i]=max(f[l+1][l+len][i]+a[i][l],f[l][l+len−1][i]+a[i][l+len])∗2 2.高精度的问题

  这个题目虽然每个数不是很大，但是最后的结果会超出64位，所以需要用到高精度，文末提供了两种高精度的方法，第一种是用__int128，第二种是自己写一个高精度模板。

3.一定要判断全0的情况，否则会有一个测试样例过不去。

AC代码(__int128)

#include
#include
using namespace std;

#define ll __int128
#define MAX 85
//__int128的输出
void print(ll x)
{
    if(x>9) print(x/10);
    putchar(x%10 + '0');
}
//__int128的输入
void input(ll &s)
{
    s = 0;
    char c = ' ';
    while(c'9') c = getchar();
    while(c>='0' && c>n>>m;
    ll a[MAX][MAX];
    ll fun[MAX][MAX][MAX] = {0};
    //读入数据
    for(int i=1;i