题目来自NOIP2007TG3
如果在考场上我现在已经歇菜了吧
今天一整天的时间全部投在这道题上，收获不小。
先上题目
题目描述Description
【问题描述】帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m 的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：1. 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；2. 每次取走的各个元素只能是该元素所在行的行首或行尾；3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分= 被取走的元素值*2i，其中i 表示第i 次取数（从1 开始编号）；4. 游戏结束总得分为m次取数得分之和。帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
输入描述Input Description
第1行为两个用空格隔开的整数n和m。第2~n+1 行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。
输出描述Output Description
输出 仅包含1 行，为一个整数，即输入矩阵取数后的最大得分。
样例输入Sample Input
2 31 2 33 4 2
样例输出Sample Output
82
数据范围及提示Data Size & Hint
样例解释
第 1 次：第1 行取行首元素，第2 行取行尾元素，本次得分为1*21+2*21=6第2 次：两行均取行首元素，本次得分为2*22+3*22=20第3 次：得分为3*23+4*23=56。总得分为6+20+56=82
【限制】60%的数据满足：1<=n, m<=30, 答案不超过1016100%的数据满足：1<=n, m<=80, 0<=aij<=1000
首先读题后，我们发现行与行之间相互独立没有干扰，这样我们就可以读一行处理一行，每一行都是一个单独的问题，相当于给了n组数据，求出答案的和。
这样我们把空间从n降到了n。
接下来开始考虑思路。不难发现，取走一部分数字后，剩下的数字总是形成一个区间。由于取走的数的个数已知，剩下的数字按顺序的权值也就知道了，由此得出，这是一个区间DP，和石子合并类似。它满足最优子结构，也满足无后效性。
用f[i][j]表示区间[i, j]的最优解，有两种解法f[i][j] = max(a[i] + 2 * f[i+1][j], a[j] + 2 * f[i][j-1]);//直接计算数的权值f[i][j] = max(a[i]*2^(m-j+i) + f[i+1][j], a[j]*2^(m-j+i) + f[i][j-1])//每次翻倍第一种，就是先做一个二的幂次方表，直接计算，很好理解。
第二种，也是更加方便的一种，只需要每次将小区间乘二即可，应用了乘法分配律的原理。进行完整个区间后，区间长度小乘的次数就多，最后的效果也是二的幂次方。应该也不难理解吧。
时间复杂度：O（n*m^2）
这样，我们这道题的框架就出来了，程序如下：
//codevs1166 矩阵取数游戏 区间DP+高精 //copyright by ametake#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=80+5;const int maxl=32;int n,m;int a[maxn],f[maxn][maxn],aa[maxn],bb[maxn],ans[maxn];int main(){int ans=0;scanf("%d%d",&n,&m);//n行m列for (int i=1;i<=n;i++){for (int j=1;j<=m;j++) scanf("%d",&a[j]);for (int j=1;j<=m;j++) f[j][j]=a[j];for (int j=1;j<=m-1;j++)//区间长度{for (int k=1;k<=m-j;k++)//起点{int l=k+j;f[k][l] = max(a[k] + 2 * f[k+1][l], a[l] + 2 * f[k][l-1]);}}ans+=2*f[1][m];}printf("%d\n",ans);return 0;} 但是等等，为什么会CE？
我们假设一种极端情况，当矩阵为80*80，且每项为1000时，结果最大，为193428131138340667952988000000。
不用数啦，这个数字是30位的。
既然这样显然我们要用高精度了。我们没有JAVA神奇的大整数，但我们也不必像pascal那样酷比手写，我们有C++的重载运算符（pas也有但是你敢用吗= =被限制的死死的一不小心就报错而且并没有什么用）
第一次手写如此大规模的高精重载，我耗费了整整一上午的时间。
因为没有任何经验，我找到了CSDN IcEnternal的代码。在这里引用一下
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;//代码非原创，来源CSDN用户IcEnternal 源地址const int power = 1; //每次运算的位数为10的power次方，在这里定义为了方便程序实现const int base = 10; //10的power次方。//要压位的时候，只需改power 和 base即可，如压万位高精，那么power = 4, base = 10000const int MAXL = 1001; //数组的长度。char a[MAXL], b[MAXL];struct num{ int a[MAXL]; num() { memset(a, 0, sizeof(a)); } //初始化 num(char *s) //将一个字符串初始化为高精度数 { memset(a, 0, sizeof(a)); int len = strlen(s); a[0] = (len+power-1) / power; //数的长度 for (int i=0, t=0, w; i < len ;w *= 10, ++i) { if (i % power == 0) { w = 1, ++t; } a[t] += w * (s[i]-'0'); } //初始化数组，这里自己模拟一下，应该很容易懂的~ } void add(int k) { if (k || a[0]) a[ ++a[0] ] = k; } //在末尾添加一个数，除法的时候要用到 void re() { reverse(a+1, a+a[0]+1); } //把数反过来，除法的时候要用到 void print() //打印此高精度数 { printf("%d", a[ a[0] ]); //先打印最高位，为了压位 或者 该高精度数为0 考虑 for (int i = a[0]-1;i > 0;–i) printf("%0*d", power, a[i]); //这里"%0*d", power的意思是，必须输出power位，不够则前面用0补足 printf("\n"); }} p,q,ans;bool operator < (const num &p, const num &q) //判断小于关系，除法的时候有用{ if (p.a[0] < q.a[0]) return true; if (p.a[0] > q.a[0]) return false; for (int i = p.a[0];i > 0;–i) { if (p.a[i] != q.a[i]) return p.a[i] < q.a[i]; } return false;}num operator + (const num &p, const num &q) //加法，不用多说了吧，模拟一遍，很容易懂{ num c; c.a[0] = max(p.a[0], q.a[0]); for (int i = 1;i <= c.a[0];++i) { c.a[i] += p.a[i] + q.a[i]; c.a[i+1] += c.a[i] / base; c.a[i] %= base; } if (c.a[ c.a[0]+1 ]) ++c.a[0]; return c;}num operator – (const num &p, const num &q) //减法，也不用多说，模拟一遍，很容易懂{ num c = p; for (int i = 1;i <= c.a[0];++i) { c.a[i] -= q.a[i]; if (c.a[i] < 0) { c.a[i] += base; –c.a[i+1]; } } while (c.a[0] > 0 && !c.a[ c.a[0] ]) –c.a[0]; //我的习惯是如果该数为0，那么他的长度也是0，方便比较大小和在末尾添加数时的判断。 return c;}num operator * (const num &p, const num &q) //乘法，还是模拟一遍。。其实高精度就是模拟人工四则运算！{ num c; c.a[0] = p.a[0]+q.a[0]-1; for (int i = 1;i <= p.a[0];++i) for (int j = 1;j <= q.a[0];++j) { c.a[i+j-1] += p.a[i]*q.a[j]; c.a[i+j] += c.a[i+j-1] / base; c.a[i+j-1] %= base; } if (c.a[ c.a[0]+1 ]) ++c.a[0]; return c;}num operator / (const num &p, const num &q) //除法，这里我稍微讲解一下{ num x, y; for (int i = p.a[0];i >= 1;–i) //从最高位开始取数 { y.add(p.a[i]); //把数添到末尾（最低位），这时候是高位在前，低位在后 y.re(); //把数反过来，变为统一的存储方式：低位在前，高位在后 while ( !(y < q) ) //大于等于除数的时候，如果小于的话，其实答案上的该位就是初始的“0” y = y – q, ++x.a[i]; //看能减几个除数，减几次，答案上该位就加几次。 y.re(); //将数反过来，为下一次添数做准备 } x.a[0] = p.a[0]; while (x.a[0] > 0 && !x.a[x.a[0]]) –x.a[0]; return x;}int main(){ scanf("%s", a); scanf("%s", b); reverse(a, a+strlen(a)); reverse(b, b+strlen(b)); p = num(a), q = num(b); ans = p + q; ans.print(); ans = p – q; ans.print(); ans = p * q; ans.print(); ans = p / q; ans.print();}上面这位前辈的代码写的相当简明易懂（相比wfwbz同学来说的确是这样），受益匪浅，但他的重载实在结构体外面写的。
我模仿着在结构体里写下了这样的代码（上述代码中并没有）：
num operator = (int b) //将一个常数赋值给高精结构体{num c;c.a[0]=0;while (b){c.a[0]++;c.a[c.a[0]]=b%base;b/=base;}return c;}以及
数最亮的星。如果有可能，我带你去远行。
