一开始思路走偏 一直在想肯定与第几次取数有关 然后做了半天没做出来
看了题解才恍然大悟 原来有个性质“可以每行分开来做 最后加起来就好了”
那就变成了一个区间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
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define ll __int128 #define N 85 using namespace std; int n,m,num[N]; ll bit[N],dp[N][N],ans; //只用关心每一行 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 len=2;len<=m;len++) { for(int st=1;st+len-1<=m;st++) { const int ed=st+len-1; dp[st][ed]=max(dp[st][ed-1]+num[ed]*bit[m-len+1],dp[st+1][ed]+num[st]*bit[m-len+1]); } } } int main() { cin>>n>>m; 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++) { cin>>num[j]; } Solve(); ans+=dp[1][m]; } if(ans==0) cout<<"0"<<endl; else write(ans); return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9824410.html
