題目描述

帥帥經(jīng)常跟同學(xué)玩一個(gè)矩陣取數(shù)游戲：對(duì)于一個(gè)給定的?�×�n×m?的矩陣，矩陣中的每個(gè)元素?��,�ai,j??均為非負(fù)整數(shù)。游戲規(guī)則如下：

1. 每次取數(shù)時(shí)須從每行各取走一個(gè)元素，共?�n?個(gè)。經(jīng)過?�m?次后取完矩陣內(nèi)所有元素；
2. 每次取走的各個(gè)元素只能是該元素所在行的行首或行尾；
3. 每次取數(shù)都有一個(gè)得分值，為每行取數(shù)的得分之和，每行取數(shù)的得分 = 被取走的元素值?×2�×2i，其中?�i?表示第?�i?次取數(shù)（從?11?開始編號(hào)）；
4. 游戲結(jié)束總得分為?�m?次取數(shù)得分之和。

帥帥想請(qǐng)你幫忙寫一個(gè)程序，對(duì)于任意矩陣，可以求出取數(shù)后的最大得分。

輸入格式

輸入文件包括?�+1n+1?行：

第一行為兩個(gè)用空格隔開的整數(shù)?�n?和?�m。

第?2～�+12～n+1?行為?�×�n×m?矩陣，其中每行有?�m?個(gè)用單個(gè)空格隔開的非負(fù)整數(shù)。

輸出格式

輸出文件僅包含?11?行，為一個(gè)整數(shù)，即輸入矩陣取數(shù)后的最大得分。

輸入輸出樣例

輸入 #1復(fù)制

2 3
1 2 3
3 4 2

輸出 #1復(fù)制

82

說明/提示

【數(shù)據(jù)范圍】

對(duì)于?60%60%?的數(shù)據(jù)，滿足?1≤�,�≤301≤n,m≤30，答案不超過?10161016。
對(duì)于?100%100%?的數(shù)據(jù)，滿足?1≤�,�≤801≤n,m≤80，0≤��,�≤10000≤ai,j?≤1000。

【題目來源】

NOIP 2007 提高第三題。

#include <bits/stdc++.h>
using namespace std;
#define N (int)(85)
const int B=1e4;
int n,m,a[N];
struct bg {int num[505],len;bg() {memset(num,0,sizeof(num));len=0;}void print() {cout << num[len];for(int i=len-1; i>0; i--) {if(!num[i])cout << "0000";else {for(int k=10; k*num[i]<B; k*=10)cout << "0";cout << num[i];}}}
} f[N][N],base[N],ans;bg operator+(bg a,bg b) {bg c;c.len=max(a.len,b.len);int jw=0;for(int i=1; i<=c.len; i++) {c.num[i]=a.num[i]+b.num[i]+jw;jw=c.num[i]/B;c.num[i]%=B;}if(jw>0)c.num[++c.len]=jw;return c;
}
bg operator*(bg a,int b) {bg c;c.len=a.len;int jw=0;for(int i=1; i<=c.len; i++) {c.num[i]=a.num[i]*b+jw;jw=c.num[i]/B;c.num[i]%=B;}while(jw>0)c.num[++c.len]=jw%B,jw/=B;return c;
}
bg max(bg a,bg b) {if(a.len!=b.len)return a.len<b.len?b:a;for(int i=a.len; i>0; i--)if(a.num[i]!=b.num[i])return a.num[i]>b.num[i]?a:b;return a;
}
void init() {base[0].num[1]=1;base[0].len=1;for(int i=1; i<=m+2; i++)base[i]=base[i-1]*2;
}
signed main() {// freopen("check.in","r",stdin);// freopen("check.out","w",stdout);cin >> n >> m;init();bg res;while(n--) {memset(f,0,sizeof(f));for(int i=1; i<=m; i++)cin >> a[i];for(int i=1; i<=m; i++)for(int j=m; j>=i; j--) {f[i][j]=max(f[i][j],f[i-1][j]+base[m-j+i-1]*a[i-1]);f[i][j]=max(f[i][j],f[i][j+1]+base[m-j+i-1]*a[j+1]);}bg mx;for(int i=1; i<=m; i++)mx=max(mx,f[i][i]+base[m]*a[i]);res=res+mx;}res.print();return 0;
}