洛谷 P1005 矩阵取数游戏（区间DP）

题目链接：https://www.luogu.com.cn/problem/P1005

会发现每一行之间没有影响，可以做n次区间DP。

设dp[i][j]表示区间[i,j]的取分最大值。如果从小区间向大区间转移，即

dp[i][j]=max(dp[i+1][j]+a[i],dp[i][j-1]+a[j])*2

这样$2^i$在转移的过程中便之间乘上了。

AC代码（无高精）：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=90;
int n,m;
ll ans;
int a[N];
ll f[N][N];
int main(){
    scanf("%d%d",&n,&m);
    for(int t=1;t<=n;t++){
        memset(f,0,sizeof(f));
        for(int i=1;i<=m;i++) scanf("%d",&a[i]);
        for(int j=0;j<=m;j++)
        for(int i=1;i+j<=m;i++){
            f[i][i+j]=max(f[i+1][i+j]+a[i],f[i][i+j-1]+a[i+j])*2;
        }
        ans+=f[1][m];
    }
    printf("%lld",ans);
    return 0;
}