NC16645（基础区间dp+高精度）

https://ac.nowcoder.com/acm/problem/16645

这道题唯一需要注意的就是高精度了吧……
思路很简单，首先发现可以每行单独处理，用dp[l,r]表示选择lr区间内的最大收益，有公式

然后就在n2内处理一行，n3处理整个矩阵即可。
值得一提的是高精度__int128不能在一般编译器上跑……并且它不支持cincout，需要自己准备io函数。

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

const int maxn=81;
__int128 dp[maxn][maxn],ans;
int a[maxn][maxn];

inline void write(__int128 x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
inline __int128 read()
{
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            a[i][j]=read();
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            dp[j][j]=a[i][j];
        for(int l=2;l<=m;l++){
            for(int k=1;k+l-1<=m;k++){
                dp[k][k+l-1]=max(dp[k][k+l-2]*2+a[i][k+l-1],dp[k+1][k+l-1]*2+a[i][k]);
            }
        }
        ans+=dp[1][m]*2;
    }
    write(ans);
}