每日一题 7月10日 矩阵取数游戏

题目链接：https://ac.nowcoder.com/acm/problem/16645
题目大意：

思路：我们可以看出，每行是独立的，那么对每行直接dp就可以了。
f[i][j]:取完区间[i, j]的数能够获得的最大值。枚举取左还是右就可以了。

#include <bits/stdc++.h>
#define LL long long
#define _int __int128
using namespace std;


inline __int128 read(){
    __int128 x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-'){
            f=-f;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return f*x;
}

void write(_int x){
    if(x<0){
        putchar('-'); x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}

_int a[105];
_int f[105][105], pw[105]={1};

_int DP(_int l, _int r, _int i){
    if(f[l][r]!=-1){
        return f[l][r];
    }
    if(l==r){
        return f[l][r]=a[l]*pw[i];
    }
    return f[l][r]=max(DP(l+1, r, i+1)+a[l]*pw[i], DP(l, r-1, i+1)+a[r]*pw[i]);
}

int main() {

    for(int i=1; i<105; i++){
        pw[i]=pw[i-1]*2;
    }
    _int ans=0;
    int n, m; scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            a[j]=read();
        }
        for(int j=1; j<=m; j++){
            for(int k=1; k<=m; k++){
                f[j][k]=-1;
            }
        }
        ans+=DP(1, m , 1);
    }
    write(ans);

    return 0;
}