题目描述 Description 【问题描述】 帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的均 为非负整数。游戏规则如下：
每次取数时须从每行各取走一个元素，共次后取完矩阵所有元素；每次取走的各个元素只能是该元素所在行的行首或行尾；每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分， 其中 开始编号）；游戏结束总得分为次取数得分之和。 帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
输入描述 Input Description 第1行为两个用空格隔开的整数。 第个用单个空格隔开的非负整数。
输出描述 Output Description 输出 仅包含1 行，为一个整数，即输入矩阵取数后的最大得分。
样例输入 Sample Input 2 3 1 2 3 3 4 2
样例输出 Sample Output 82
数据范围及提示 Data Size & Hint 样例解释 第1次：第1行取行首元素，第2行取行尾元素，本次得分为 第2次：两行均取行首元素，本次得分为 第3次：得分为 【限制】
题解 可以看出每行是相互独立的，所以可以先考虑每一行。问题简化为每次可以取一列数的第一个或最后一个，第，问取这一列数可获得的最大得分。 这样就可以很显然地看出是区间dp了。 用里的数后所获得的最大得分，，应有： 即第一次取的是头上的元素和第一次取的是尾部的元素取最大值。 然后遍dp，把每行的最大值加起来就得到了答案。 本题需要写高精。
Code
;const int maxnum = 35;ll;//所以开long longint n, m, map[81][81];//下面一坨高精度翔，可以先不理它struct highNum{ll num[maxnum];highNum(int length = 1){memset(num, 0, sizeof(num));num[0] = length;}highNum operator = (highNum b){memcpy(num, b.num, sizeof(b.num));return *this;}highNum operator = (int b){*this = highNum();num[num[0]] = b;return *this;}bool operator < (const highNum& b) const{if(num[0] < b.num[0]) return true;if(num[0] == b.num[0]){for(int i = num[0]; i >= 1; –i){if(num[i] > b.num[i]) return false;if(num[i] < b.num[i]) return true;}}return false;}highNum operator + (const highNum& b) const{highNum c = highNum(max(num[0], b.num[0]));for(int i = 1; i <= c.num[0]; ++i){c.num[i] += num[i] + b.num[i];c.num[i + 1] += c.num[i] / M;c.num[i] %= M;}while(c.num[c.num[0] + 1] > 0){++c.num[0];c.num[c.num[0] + 1] += c.num[c.num[0]] / M;c.num[c.num[0]] %= M;}return c;}highNum operator * (const int b) const{highNum c = highNum(num[0]);for(int i = 1; i <= c.num[0]; ++i){c.num[i] += num[i] * b;c.num[i + 1] += c.num[i] / M;c.num[i] %= M;}while(c.num[c.num[0] + 1] > 0){++c.num[0];c.num[c.num[0] + 1] += c.num[c.num[0]] / M;c.num[c.num[0]] %= M;}while(c.num[c.num[0]] == 0 && c.num[0] > 1) –c.num[0];return c;}highNum operator * (const highNum& b) const{highNum c = highNum(num[0] + b.num[0]);for(int i = 1; i <= num[0]; ++i) for(int j = 1; j <= b.num[0]; ++j){c.num[i + j – 1] += num[i] * b.num[j];c.num[i + j] += c.num[i + j – 1] / M;c.num[i + j – 1] %= M;}while(c.num[c.num[0] + 1] > 0){++c.num[0];c.num[c.num[0] + 1] += c.num[c.num[0]] / M;c.num[c.num[0]] %= M;}while(c.num[c.num[0]] == 0 && c.num[0] > 1) –c.num[0];return c;}};ostream& operator << (ostream& o, highNum& b){o << b.num[b.num[0]];o.setf(ios::fixed);o.width(8);o.fill(‘0’);for(int i = b.num[0] – 1; i >= 1; –i) o << b.num[i];return o;}//这里才开始真正解题highNum ans, f[81][81], pw[81];void init(){cin >> n >> m;for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j)cin >> map[i][j];//读入这个矩阵pw[1] = 2;//pw来存2的若干次方for(int i = 2; i <= m; ++i) pw[i] = pw[i – 1] * 2;}void work(int row)//dp第row行{for(int i = 1; i <= m; ++i) for(int j = 1; j <= m; ++j)f[i][j] = highNum();//对每一行dp要先清空dp数组for(int i = 1; i <= m; ++i) f[i][i] = pw[m] * map[row][i];for(int p = 1; p < m; ++p) for(int i = 1; i <= m – p; ++i){int j = i + p;f[i][j] = max(f[i + 1][j] + pw[m – p] * map[row][i], f[i][j – 1] + pw[m – p] * map[row][j]);}ans = ans + f[1][m];}int main(){init();for(int i = 1; i <= n; ++i) work(i);cout << ans;return 0;}
明天是世上增值最快的一块土地，因它充满了希望
