這是一道NOIp07年的原題，題目本身并不難。

題目看上去很熟悉，第一次看完題目后往貪心的方面去想的，設計了兩種貪心策略：1、每次從兩端選取最小的數字；2、從后向前倒推，使最后一次取到的數字最大。兩種貪心是不同的，而且都是錯的，競賽原題中給的樣例數據都過不去。但是如果不會DP的話，感覺上第二種貪心更易導致最優解（只是感覺）。

動態規劃：分析出實際上行與行之間是互不影響的，就是說對每行的決策可以單獨進行。給定一個區間[i,j]，每次可能的決策是選擇a[i]或者a[j]，這樣一個區間被分成了更小的一部分，考慮動態規劃。容易寫出狀態轉移方程：d[i][j]=max(d[i+1][j]+w[i],d[i][j-1]+w[j])，其中w[i]可以很容易推出來，不再給出。

此題需要注意的地方：1、需要預處理2^n，因為要被多次用到；2、要用高精度，高精度一般用得比較少，一開始我是把高精度結果按返回值處理，出了錯；后來改成傳記錄結果的地址，在高精度函數中直接修改數值，第8、9兩個點超時；分析了原因之后，發現是高精度時傳遞加數和乘數耗了太多時，就把加數、乘數、結果全部地址傳遞，vijos上全部數據9ms。導致我對于一直沒有太多注意的高精度感慨萬千。

以下是我的代碼：

#include<stdio.h>
#define size 81
#define max(a,b) (a>b?a:b)
typedef struct
{
    int len;
    long s[30];
}high;
int n,m,a[size][size]={0};
high d[120][120],Two_[size];
high zero={1,{0}},one={1,{1}},two={1,{2}};
void add(high *c,high *a,high *b)
{// 高精度加上高精度 
    int l,i;
    l=(a->len>b->len?a->len:b->len);
    for(i=0;i<=l;i++)
      c->s[i]=0;
    for(i=0;i<l;i++)
    {
       c->s[i]+=a->s[i]+b->s[i];
       if(c->s[i]>=100000)
       {
          c->s[i+1]++;
          c->s[i]%=100000;
       }
    }
    c->len=l;
    if(c->s[c->len]!=0) c->len++;
}
void mul(high *c,high *a,long b)
{// 高精度乘上單精度 
    int i;
    for(i=0;i<=a->len;i++)
      c->s[i]=0;
    for(i=0;i<a->len;i++)
    {
       c->s[i]+=a->s[i]*b;
       if(c->s[i]>=100000)
       {
          c->s[i+1]+=c->s[i]/100000;
          c->s[i]%=100000;
       }
    }
    c->len=a->len;
    if(c->s[c->len]!=0) c->len++;
}
int high_max(high *a,high *b)
{// 比較單精度數 
    long i;
    if(a->len>b->len) return 1;
    if(a->len<b->len) return 0;
    for(i=a->len-1;i>=0;i--)
      if(a->s[i]>b->s[i])
        return 1;
      else if(a->s[i]<b->s[i])
        return 0;
    return 1;
}
void print(high *a)
{// 輸出高精度 
    int i;
    printf("%ld",a->s[a->len-1]);
    for(i=a->len-2;i>=0;i--)
    {
       if(a->s[i]<10000) printf("0");
       if(a->s[i]<1000) printf("0");
       if(a->s[i]<100)   printf("0");
       if(a->s[i]<10)    printf("0");
       printf("%ld",a->s[i]);
    }
    printf("\n");
}
void init()
{// 打開文件 讀入 預處理2^n 初始化表 
    int i,j;
    scanf("%ld%ld",&n,&m);
    for(i=1;i<=n;i++)
      for(j=1;j<=m;j++)
        scanf("%ld",&a[i][j]);
    Two_[0]=one;
    Two_[1]=two;
    for(i=2;i<=m;i++)
      mul(&Two_[i],&Two_[i-1],2);
    for(i=0;i<=m;i++)
      for(j=0;j<=m;j++)
        d[i][j]=zero;
}
high dp(int nn)
{// 對第 nn 行動態規劃 
    int i,j;
    high t1,t2,t3,t4;
    for(j=0;j<=m-1;j++)
      for(i=1;i<=m-j;i++)
      {
         mul(&t1,&Two_[m-j],a[nn][i]);
         add(&t2,&d[i+1][i+j],&t1);
         mul(&t3,&Two_[m-j],a[nn][i+j]);
         add(&t4,&d[i][i+j-1],&t3);
         if(high_max(&t2,&t4))
           d[i][i+j]=t2;
         else d[i][i+j]=t4;
      }
    return d[1][m];
}
void end()
{
    int i;
    high t1,t2,ans=zero;
    for(i=1;i<=n;i++)
    {
       t1=ans;
       t2=dp(i);
       add(&ans,&t1,&t2);
    }
    print(&ans);
}
int main()
{
    init();
    end();
return 0;
}