网站推广渠道/石家庄学院
题目描述 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 3
1 2 3
3 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, 答案不超过1016
100%的数据满足：1<=n, m<=80, 0<=aij<=1000
突然兴起想写高精，正好还想写dp，于是就写了这个水题…
就除法和乘法有点问题…亏我到现在还没忘……话说压9位高精跑得飞快哈哈哈
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;typedef long long LL;
const int WIDTH = 9;
const int BASE = 1000000000;
const int INF = 1000000010;
const int SZ = 5;struct bign{int num[SZ],len;bign() { memset(num,0,sizeof(num)); len = 1; }bign(LL x){memset(num,0,sizeof(num)); len = 0;do{num[++ len] = x % BASE;x /= BASE;}while(x);}
};bool operator <(const bign &a,const bign &b)
{if(a.len != b.len) return a.len < b.len;for(int i = a.len;i >= 1;i --)if(a.num[i] != b.num[i]) return a.num[i] < b.num[i];return false;
}bign operator +(const bign &a,const bign &b)
{bign ans;int i = 1,x = 0;while(i <= a.len || i <= b.len){x += a.num[i] + b.num[i];ans.num[i] = x % BASE;x /= BASE;i ++;}ans.num[i] = x;ans.len = i;while(ans.len && !ans.num[ans.len]) ans.len --;return ans;
}bign operator -(const bign &a,const bign &b)
{bign ans;ans.len = max(a.len,b.len);int x = 0;for(int i = 1;i <= a.len;i ++){x = a.num[i] - b.num[i] + BASE + x;ans.num[i] = x % BASE;x = x / BASE - 1;}while(ans.len && !ans.num[ans.len]) ans.len --;return ans;
}bign operator *(const bign &a,const bign &b)
{bign ans;ans.len = a.len + b.len;for(int i = 1;i <= a.len;i ++){LL x = 0;for(int j = 1;j <= b.len;j ++){x = ans.num[i + j - 1] + (LL)a.num[i] * b.num[j] + x;ans.num[i + j - 1] = x % BASE;x /= BASE;}ans.num[i + b.len] = x;}while(ans.len && !ans.num[ans.len]) ans.len --;return ans;
}
bool smaller(const bign &a,const bign &b,int d)
{if(a.len + d != b.len) return a.len + d < b.len;for(int i = a.len;i >= 1;i --)if(a.num[i] != b.num[i + d]) return a.num[i] < b.num[i + d];return true;
}void jian(bign &a,const bign &b,int d)
{int x = 0;for(int i = 1;i <= a.len - d;i ++){x = a.num[i + d] - b.num[i] + BASE + x;a.num[i + d] = x % BASE;x = x / BASE - 1;}while(a.len && !a.num[a.len]) a.len --;
}bign operator /(const bign &a,const bign &b)
{bign ans;ans.len = max(1,a.len - b.len + 1);bign num = a,mid[32];mid[0] = b;for(int i = 1;i <= 30;i ++) mid[i] = mid[i - 1] * 2;for(int i = a.len - b.len;i >= 0;i --){int tmp = 1 << 30;for(int j = 30;j >= 0;j --){if(smaller(mid[j],num,i)){jian(num,mid[j],i);ans.num[i + 1] += tmp;}tmp >>= 1;}}while(ans.len && !ans.num[ans.len]) ans.len --;return ans;
}void printf(const bign &a)
{printf("%d",a.num[a.len]);for(int i = a.len - 1;i >= 1;i --)printf("%09d",a.num[i]);printf(" ");
}int maps[233][233],n,m;bign dp[233][233],mi[233];bign ask(int x)
{memset(dp,0,sizeof(dp));dp[0][1] = maps[x][m] * 2;dp[1][0] = maps[x][1] * 2;for(int i = 0;i <= m;i ++){for(int j = 0;j <= m - i;j ++){if(i + j == 1) continue;if(i - 1 >= 0)dp[i][j] = max(dp[i][j],dp[i - 1][j] + maps[x][i] * mi[i + j]);if(j - 1 >= 0)dp[i][j] = max(dp[i][j],dp[i][j - 1] + maps[x][m - j + 1] * mi[i + j]);}}bign ans = 0;for(int i = 0;i <= m;i ++)ans = max(ans,dp[i][m - i]);return ans;
}int main()
{scanf("%d%d",&n,&m);for(int i = 1;i <= n;i ++)for(int j = 1;j <= m;j ++)scanf("%d",&maps[i][j]);mi[0] = 1;for(int i = 1;i <= m;i ++)mi[i] = 2 * mi[i - 1];bign ans = 0;for(int i = 1;i <= n;i ++)ans = ans + ask(i);printf(ans);return 0;
}