[每日一题]矩阵取数游戏

解题报告：
看到 每行取数的得分 = 被取走的元素值 * 2^i，由于i是递增的。所以第一想法就是把大的留在最后，即每次取每行首尾最小的那个，但是样例二则轻易的否定这种做法。

考虑到其实每行的贡献是独立的，相当于把每次操作拆成n次操作，那么我们考虑怎么得到一行的最大值。

可以发现每次操作的区间是不断缩小的，可以看出是一个区间dp，
我们让dp[i][j]为 [i j] 取完的最大值，所以
dp[i][j] = max {dp[i+1][j]+a[i],dp[i][j-1]+a[j]} ;
就相当于在区间[i j] 时取首还是尾。

用 __int128

#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,a,b) for(ll i=(a);i>=(b);i--)
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
const ll  inf  = 0x3f3f3f3f3f3f3f3f;
const int mod  = 1e9  + 7;
const int maxn = 1e6  + 4;
const int N    = 1000 + 5;
ll qpow(ll x,ll y){ll ans=1;x%=mod;assert(y>=0);while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;}
//ctrl + h 查询 替换    ctrl + shift + t 恢复刚刚关闭的标签
//ctrl + shift + d/k 复制/删除当前行 
//alt  + shift + 1/2/3/4 分屏
inline void print(__int128 x) {
    if(x<0){putchar('-'); x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int n,m,a[N][N];
__int128 dp[N][N];
int main() {
    //freopen("input.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            scanf("%d",&a[i][j]);
        }
    }
    __int128 ans=0;
    for(int i=1;i<=n;i++) {
        memset(dp,0,sizeof dp);
        for(int j=1;j<=m;j++) dp[j][j]=a[i][j]*2;
        for(int len=2;len<=m;len++) {
            for(int st=1;st+len-1<=m;st++) {
                int ed=st+len-1;
                dp[st][ed]=max(dp[st+1][ed]+a[i][st],dp[st][ed-1]+a[i][ed])*2;
            }
        }
        ans=ans+dp[1][m];
    }
    print(ans);puts("");
    return 0;
}