点我博客食用更佳

（注：新oj由于数据过弱，甚至可能可以不用int128（我没试过doge））

矩阵取数游戏

~众所周知，一般而言，随着经济社会的发展...~

（以上省略114514字）...今天，小编就来给大家带来矩阵取数游戏的...

首先介绍一个知识:

__int128！

首先，int128和普通的int在运算上没什么不同，但是 数据范围是ll的平方！

但是两者还是有点区别的。比如：

int128不能直接cin>>读取和cout<<输出，所以要自己写一个快读快输。

借助高精思路，甚至不需要太多，就能得出快读快写：

inline void input(__int128 &s)
{
    s=0;
    char c=' ';
    while(c>'9'||c<'0') c=getchar();
    while(c>='0'&&c<='9')
    {
        s=s*10+c-'0';
        c=getchar();
    }
}

inline void output(__int128 x)
{
    if(x>9)
        output(x/10);
    putchar(x%10+'0');
}

而本题，很明显需要使用区间DP。（注：一下num均表示一行 ​~（三维数组也问题不大）~​。）

以nu[i][j]表示所有数字（当然也可以用一个随时重置的一维数组）每行将一个nu[i]传到函数里，函数的参数是一个一维数组nn[]，这样读更加方便一点.

使用num[i][j]来储存每行区间[i,j]的最大结果。由于DP的最优解原理，每个[i,j]都是当前状态下最大值。

通过遍历从0-m的步长l，再遍历i为1-m，设j=i+m，可得出以下结论：

而每个num[i][j]都是由num[i-1][j]取nn[i]或num[i][j+1]取num[j]计算而来的。

再看提议，其实强算也问题不大，但更建议使用题解里的一种算法。由于每次是取自身的2^n，故每次取点可看作先取一次自己，然后对后面的总数进行一次*2

所以可以得出转移方程：

num[i][j]=max(2 num[i-1][j] + 2 a[i], 2 num[i][j+1] + 2 a[j])

以下代码：

#include <bits/stdc++.h>
using namespace std;

inline void input(__int128 &s)
{
    s=0;
    char c=' ';
    while(c>'9'||c<'0') c=getchar();
    while(c>='0'&&c<='9')
    {
        s=s*10+c-'0';
        c=getchar();
    }
}

inline void output(__int128 x)
{
    if(x>9)
        output(x/10);
    putchar(x%10+'0');
}

__int128 ans=0;
__int128 nu[90][90],num[90][90];
int n,m;

__int128 line(__int128 nn[])
{
    for(int l=0;l<=m;l++){
        for(int i=1;i<=m-l;i++){
            int k=i+l;
            num[i][k]=max(2*num[i+1][k]+2*nn[i],2*num[i][k-1]+2*nn[k]);
        }
    }
    return num[1][m];
}

signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        memset(num,0,sizeof(num));
        for (int j=1;j<=m;j++){
            input(nu[i][j]);
        }
        ans+=line(nu[i]);
    }
    output(ans);
    return 0;
}