NC16645（矩阵取数游戏 ）

感受

思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 100000 + 10;
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;
}
inline void print(__int128 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
__int128 dp[100][100][100];///dp[l][r] 表示剩余[l, r]的最大值
int a[100][100];
int n, m;
__int128 f[100], ans;
void init(){
    f[0] = 1;
    for(int i = 1; i <= m; i++){
        f[i] = f[i - 1] * 2;
    }
}
__int128 get(int x){
    for(int len = m - 1; len >= 1; len--){
        for(int l = 1, r; ; l++){
            r = l + len - 1;
            if(r > m) break;
            if(l > 1) dp[x][l][r] = dp[x][l - 1][r] + (__int128)1 * a[x][l - 1] * f[m - len];
            if(r < m) dp[x][l][r] = max(dp[x][l][r], dp[x][l][r + 1] + (__int128)1 * a[x][r + 1] * f[m - len]);
        }
    }
    __int128 tmp = 0;
    for(int i = 1; i <= m; i++) tmp = max(tmp, dp[x][i][i] + (__int128)1 * a[x][i] * f[m]);
    return tmp;
}
int main(){
    scanf("%d%d", &n, &m);
    init();
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            scanf("%d", &a[i][j]);
        }
        ans += get(i);
    }
    print(ans);
    return 0;
}