记录编号	96927	评测结果	AAAAAAAAAA
题目名称	[NOIP 2007]矩阵取数游戏	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	1.422 s
提交时间	2014-04-15 23:02:47	内存使用	9.61 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <functional>
using namespace std;
struct bign
{
  int num[300];
  int end;
  bign()
  {
    memset(this->num,0,sizeof(this->num));
    this->end=1;
  }
  bign operator =(const int a)
  {
    int k=a;
    memset(this->num,0,sizeof(this->num));
    this->end=0;
    while (k!=0)
    {
      this->end++;
      this->num[this->end]=k%10000;
      k=k/10000;
    }
  }
  bign (int a)
  {
    *this=a;
  }
  bign operator +(const bign a) const
  {
     bign sum;
     memset(sum.num,0,sizeof(sum.num));
     int len;
     if (this->end>a.end)
       len=this->end;
     else
       len=a.end;
     int i;
     for(i=1;i<=len;i++)
     {
       sum.num[i]+=this->num[i]+a.num[i];
       if (sum.num[i]>10000)
       {
         sum.num[i+1]++;
         sum.num[i]=sum.num[i]%10000;
       }
     }
     sum.end=i-1;
     if (sum.num[i]!=0)
       sum.end++;
    return sum;
  }
  bign operator +(const int a) const
  {
    bign l=a;
    return *this+l;
  }
  bign operator *(const bign a) const
  {
    bign product;
    memset(product.num,0,sizeof(product.num));
    for(int i=1;i<=this->end;i++)
      for(int j=1;j<=a.end;j++)
      {
        product.num[i+j-1]+=this->num[i]*a.num[j];
        if (product.num[i+j-1]>10000)
        {
          product.num[i+j]+=product.num[i+j-1]/10000;
          product.num[i+j-1]%=10000;
          if (i+j>product.end)
            product.end=i+j;
        }
        if (i+j-1>product.end)
          product.end=i+j-1;
      }
    return product;
  }
  bign operator *(const int q) const
  {
    bign k=q;
    k=k*(*this);
    return k;
  }
  bool operator >(const bign a)
  {
    int len;
    if (this->end>a.end)
      len=this->end;
    else
      len=a.end;
    for(int b=len;b>=1;b--)
    {
      if (this->num[b]==a.num[b])
        continue;
      if (this->num[b]>a.num[b])
        return true;
      else
        return false;
    } 
    return false;
  }
  void print()
  {
    for(int a=this->end;a>=1;a--)
    {
      if (a!=this->end)
        if (this->num[a]<10)
          printf("000");
        else if (this->num[a]<100)
          printf("00");
        else if (this->num[a]<1000)
          printf("0");
      printf("%d",this->num[a]);
    }
    printf("\n");
  }
};
bign quickpow(int k)
{
  if (k==1)
  {
    bign a=2;
    return a;
  }
  bign a=quickpow(k/2);
  a=a*a;
  if (k%2)
    a=a*2;
  int b=210;
  while (a.num[b]==0)
    b--;
  a.end=b;
  return a;
}
bign f[90][90];
int main()
{
 /* bign a=65;
  bign b=98;
  bign c=a+b;
  c.print();*/
  freopen("game.in","r",stdin);
  freopen("game.out","w",stdout);
  int row,line;
  scanf("%d%d",&row,&line);
  bign sum;
  for (int nrow=1;nrow<=row;nrow++)
  {
    int c[100];
    int nline;
    for(nline=1;nline<=line;nline++)
      scanf("%d",&c[nline]);
    f[0][0]=0;
    for(int k=1;k<=line;k++)
    {
      bign powed=quickpow(k);
      for(int s=0;s<=k;s++)
      {
        bign a,b;
        if (s>0)
        {
           a=powed*c[s];
           a=a+f[s-1][k-s];
        }
        if (k-s>0)
        {
           b=powed*c[line-k+s+1];
           b=b+f[s][k-s-1];
        }
        if (a>b)
          f[s][k-s]=a;
        else
          f[s][k-s]=b;
      }
    }
    bign max=0;
    for(int a=0;a<=line;a++)
    {
      if (f[a][line-a]>max)
        max=f[a][line-a];
    }
    /*for(int a=0;a<=line;a++)
      f[0][a].print();*/
   //max.print();
   sum=max+sum;
   
  }
  sum.print();
  //bign a=quickpow(20);
  //a.print();
  //system("pause");
  return 0;
}