题解 | 矩阵取数游戏-NOIP2007提高组复赛C题

输入描述:

题目看上去很熟悉，第一次看完题目后往贪心的方面去想的，设计了两种贪心策略：1、每次从两端选取最小的数字；2、从后向前倒推，使最后一次取到的数字最大。两种贪心是不同的，而且都是错的，竞赛原题中给的样例数据都过不去。但是如果不会DP的话，感觉上第二种贪心更易导致最优解（只是感觉）。

动态规划：分析出实际上行与行之间是互不影响的，就是说对每行的决策可以单独进行。给定一个区间[i,j]，每次可能的决策是选择a[i]或者a[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;
}