代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cctype> 5 #include <iostream> 6 using namespace std; 7 8 #define res register int 9 inline int read() 10 { 11 int x(0),f(1); char ch; 12 while(!isdigit(ch=getchar())) if(ch==‘-‘) f=-1; 13 while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-‘0‘,ch=getchar(); 14 return f*x; 15 } 16 17 const int N=80+5; 18 int n,m; 19 __int128 f[N][N],ans,a[N],p[N]; 20 21 inline void print(__int128 x) 22 { 23 if(!x) return; 24 print(x/10); 25 putchar(x%10+‘0‘); 26 } 27 28 int main() 29 { 30 n=read(); m=read(); 31 p[0]=1; 32 for(res i=1 ; i<=m ; i++) p[i]=p[i-1]*2; 33 for(res i=1 ; i<=n ; i++) 34 { 35 memset(f,0,sizeof(f)); 36 for(res j=1 ; j<=m ; j++) a[j]=read(),f[j][j]=a[j]*p[m]; 37 for(res len=2 ; len<=m ; len++) 38 { 39 for(res l=1 ; l<=m-len+1 ; l++) 40 { 41 int r=l+len-1; 42 f[l][r]=max(f[l+1][r]+a[l]*p[m-len+1],f[l][r-1]+a[r]*p[m-len+1]); 43 } 44 ans+=f[1][m]; 45 } 46 } 47 if(!ans) printf("0"); 48 else print(ans); 49 return 0; 50 }
原文:https://www.cnblogs.com/wmq12138/p/10365623.html