解题报告:
看到 每行取数的得分 = 被取走的元素值 * 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; }