P1005 [NOIP2007 提高组] 矩阵取数游戏

题目输入输出

我寻思这不就是一道普普通通的dp吗，然后被500多亿大的数据给毒打了，高精度就涉及到我的知识盲区了 _int128 真是个神奇的东西，不过需要手动输入输出一下

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 85;

__int128 v[MAXN][MAXN];
__int128 dp[MAXN][MAXN];

__int128 func(int l, int m){
    memset(dp, 0, sizeof(dp));
    __int128 ans = 0;
    for(int i = 0; i < m; i++){
        for(int j = m; j >= i; j--){
            int cnt = m - (j - i);
            if(i == 0)
                dp[i][j] = dp[i][j + 1] + (v[l][j] << cnt);
            else
                dp[i][j] = max(dp[i - 1][j] + (v[l][i - 1] << cnt), dp[i][j + 1] + (v[l][j] << cnt));
        }
        if(dp[i][i] > ans)
            ans = dp[i][i];
    }
    return ans;
}
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');
}
int main(){
    int m, n;
    cin >> n >> m;
    memset(v, 0, sizeof(v));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            input(v[i][j]);
        }
    }
    __int128 ans = 0;
    //memset(dp, 0, sizeof(dp));
    
    for(int i = 0; i < n; i++){
        ans += func(i, m);
    }
    output(ans);
    return 0;
}