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

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

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

此題需要注意的地方：1、需要預(yù)處理2^n，因?yàn)橐欢啻斡玫剑?、要用高精度，高精度一般用得比較少，一開始我是把高精度結(jié)果按返回值處理，出了錯(cuò)；后來改成傳記錄結(jié)果的地址，在高精度函數(shù)中直接修改數(shù)值，第8、9兩個(gè)點(diǎn)超時(shí)；分析了原因之后，發(fā)現(xiàn)是高精度時(shí)傳遞加數(shù)和乘數(shù)耗了太多時(shí)，就把加數(shù)、乘數(shù)、結(jié)果全部地址傳遞，vijos上全部數(shù)據(jù)9ms。導(dǎo)致我對(duì)于一直沒有太多注意的高精度感慨萬千。

以下是我的代碼：

#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)
{// 比較單精度數(shù) 
    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()
{// 打開文件 讀入 預(yù)處理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)
{// 對(duì)第 nn 行動(dòng)態(tài)規(guī)劃 
    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;
}