一开始思路走偏 一直在想肯定与第几次取数有关 然后做了半天没做出来
看了题解才恍然大悟 原来有个性质“可以每行分开来做 最后加起来就好了”
那就变成了一个区间DP 我们设dp[i][j]表示从ｉ到ｊ闭区间的最大价值。（只考虑当前行）
那么dp[i][j]肯定是从i的右边/j的左边转移来的 则有dp[st][ed] = max( dp[st][ed-1] + num[ed] * 2^(m-len+1) , dp[st+1][ed] + num[st] * 2^(m-len+1));
然后答案就是dp[1][m] 最后把所有答案相加就好
多说一句 一般来说区间DP的写法都是先枚举区间长度 随后枚举起点
都8012年了 谁还会让你去写高精 果断__int128
#include<bits/stdc++.h> #define ll __int128 #define N 85 using namespace std; ll n,m,bit[N]; ll dp[N][N],num[N],ans; //只用关心每一行 inline int read() { int s=0,f=1; char c=getchar(); while(c<'0' || c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0' && c<='9') { s=s*10+c-48; c=getchar(); } return s*f; } void write(ll x) { if(x==0) return; else if(x) write(x/10); putchar(x+'0'); } inline void Solve() { memset(dp,0,sizeof(dp)); for(int i=1;i<=m;i++) dp[i][i]=num[i]*bit[m]; for(int i=1;i<=m;i++) { for(int j=m;j>=i;j--) { dp[i][j]=max(dp[i-1][j]+num[i-1]*bit[m-j+i-1],dp[i][j+1]+num[j+1]*bit[m-j+i-1]); } } } int main() { n=read();m=read(); bit[0]=1; for(int i=1;i<=m;i++) bit[i]=bit[i-1]*2; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { num[j]=read(); } Solve(); ll maxv=0; for(int i=1;i<=m;i++) maxv=max(maxv,dp[i][i]+bit[m]*num[i]); ans+=maxv; } if(ans==0) cout<<"0"<<endl; else write(ans); return 0; }