NOIP 2007 矩阵取数

首先，我们必须发现：
行之间是没有关系的。所以，如果每一行都可以取得最大分，总分就最大。
因此，只需要一行一行地计算。

观察题目样例：
4 5 0 5
可以发现，取数次数k与剩余数字t的关系，k + t = m；
如果我们用f[l][i]表示剩余的数字是从第i个数字开始的l个数字，即第[i,i + l -1]区间内数字，那么，这个状态可以从两个方向到达：

从[i,i + l]中取出最右边的数;从[i - 1,i + l]中取出最左边的数。

因此，容易得出转移方程：
f[l][i] =
max{f[l + 1][i] + 2^(m-k) * value[row][i + l],f[l + 1][i - 1] + 2^(m-k) * value[row][i - 1]}

需要注意区间在在两侧的情况，此时没有更右边的数或者更左边的数。

最后输出f[i][0]，0 <= i < m，中的最大值即可。

此外，由于题目给出的数据很大，要用到2的80次方，因此需要高精度乘法和加法，还有高精度比较大小。

我的代码

001 //2007 NOIP 矩阵取数
002 //DP，高精
003 #include <stdio.h>
004 #include <stdlib.h>
005 #include <string.h>
006 #define MXN 81
007
008 typedef struct bignum
009 {
010     long num[40];
011     int len;
012 }bignum;
013
014 bignum base[MXN];
015 bignum a[MXN][MXN];
016 bignum opt[MXN][MXN];
017 bignum ans;
018 int m,n;
019
020 void pt_big(bignum);
021
022 int get_max(int a,int b)
023 {
024     if(a > b)   return a;
025     return b;
026 }
027
028 bignum plus(bignum a,bignum b)
029 {
030     int x,i;
031     bignum sum;
032     for(i = x = 0;i < get_max(a.len,b.len);i ++)
033     {
034         x += a.num[i] + b.num[i];
035         sum.num[i] = x % 10;
036         x /= 10;
037     }
038     sum.len = i;
039     if(x > 0)
040     {
041         sum.num[sum.len] = x;
042         sum.len ++;
043     }
044     return sum;
045 }
046
047 bignum multiply(bignum a,bignum b)
048 {
049     bignum product;
050     memset(&product,0,sizeof(bignum));
051     int i,j;
052     for(i = 0;i < a.len;i ++)
053         for(j = 0;j < b.len;j ++)
054         {
055             product.num[i + j] += a.num[i] * b.num[j];  //为了优化时间，此处不考虑进位，因此bignum.num要用long
056         }
057     product.len = a.len + b.len + 2;
058     for(i = 0;i < product.len;i ++)
059     {
060         product.num[i + 1] += product.num[i] / 10;  //在这里进位
061         product.num[i] %= 10;
062     }
063     while(product.len >= 0 && product.num[product.len] == 0)
064         product.len --;  //出去前面多余的0
065     product.len += 1;
066     return product;
067 }
068
069 int larger(bignum a,bignum b)
070 {
071     if(a.len > b.len)   return 1;
072     if(a.len < b.len)   return 0;
073     int i;
074     for(i = a.len - 1;i >= 0;i --)
075     {
076         if(a.num[i] > b.num[i]) return 1;
077         else if(a.num[i] < b.num[i])    return 0;
078     }
079     return 0;
080 }
081
082 bignum solve(int row)
083 {
084     bignum max;
085     bignum tmp;
086     int l,i;
087     memset(opt,0,sizeof(opt));
088     for(l = m - 1;l >= 0;l --)
089     {
090         for(i = 0;i + l <= m;i ++)
091         {
092             memset(&max,0,sizeof(bignum));
093             if(i > 0)
094             {
095                 tmp = plus(opt[l + 1][i - 1],multiply(base[m - l],a[row][i - 1]));
096                 max = tmp;
097             }
098             if(i + l < m)
099             {
100                 tmp = plus(opt[l + 1][i],multiply(base[m - l],a[row][i + l]));
101                 if(larger(tmp,max))
102                     max = tmp;
103             }
104             opt[l][i] = max;
105         }
106     }
107     memset(&max,0,sizeof(bignum));
108     for(i = 0;i < m;i ++)
109         if(larger(opt[0][i],max))   max = opt[0][i];
110     return max;
111 }
112
113 bignum covert(char *str)  //字符串转高精度
114 {
115     bignum a;
116     a.len = strlen(str);
117     int i;
118     for(i = 0;i < a.len;i ++)
119         a.num[i] = str[a.len - i - 1] - '0';
120     return a;
121 }
122
123 void pt_big(bignum a)  //输出高精度数值
124 {
125     int i;
126     if(a.len == 0)  printf("0");  //注意0的特例
127     for(i = a.len - 1;i >= 0;i --)
128         printf("%ld",a.num[i]);
129     printf("\n");
130 }
131
132 int main()
133 {
134     int i,j;
135     char tmp[10];
136     scanf("%d%d\n",&n,&m);
137     //create base table
138     base[1].len = 1;
139     base[1].num[0] = 2;
140     for(i = 2;i <= m;i ++)
141         base[i] = multiply(base[i - 1],base[1]);
142     //read data
143     for(i = 0;i < n;i ++)
144         for(j = 0;j < m;j ++)
145         {
146             scanf("%s",tmp);
147             a[i][j] = covert(tmp);
148         }
149     //end reading
150     memset(&ans,0,sizeof(bignum));
151     for(i = 0;i < n;i ++)
152         ans = plus(ans,solve(i));  //计算每行可获得的最大分
153     pt_big(ans);
154     return 0;
155 }