简答题
偏难
#23620
矩阵取数游戏 【问题描述】 帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的 n*m 的矩阵,矩阵中的每个元素 aij均为非负整数。游戏规则如下: 1. 每次取…
矩阵取数游戏
【问题描述】
帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的 n*m 的矩阵,矩阵中的每个元素 aij均为非负整数。游戏规则如下:
1. 每次取数时须从每行各取走一个元素,共 n 个。m 次后取完矩阵所有元素;
2. 每次取走的各个元素只能是该元素所在行的行首或行尾;
3. 每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分 = 被取走的元素值*2i,其中 i 表示第 i 次取数(从 1 开始编号);
4. 游戏结束总得分为 m 次取数得分之和。
帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。
【输入】
输入文件 game.in 包括 n+1 行:
第 1 行为两个用空格隔开的整数 n 和 m。
第 2~n+1 行为 n*m 矩阵,其中每行有 m 个用单个空格隔开的非负整数。
【输出】
输出文件 game.out 仅包含 1 行,为一个整数,即输入矩阵取数后的最大得分。
【输入输出样例 1】

【输入输出样例 1 解释】
第 1 次:第 1 行取行首元素,第 2 行取行尾元素,本次得分为 1*21+2*21=6
第 2 次:两行均取行首元素,本次得分为 2*22+3*22=20
第 3 次:得分为 3*23+4*23=56。总得分为 6+20+56=82
【输入输出样例 2】

【输入输出样例 3】

【限制】
60%的数据满足:1<=n, m<=30, 答案不超过 10^16
100%的数据满足:1<=n, m<=80, 0<=aij<=1000
答案与解析
正确答案:<p style="text-align: left;">#include <cstdio></p><p style="text-align: left;">#include <cstring></p><p style="text-align: left;">#include <algorithm></p><p style="text-align: left;">#include <iostream></p><p style="text-align: left;">#include <iomanip></p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int maxnum = 35;</p><p style="text-align: left;">const int M = 100000000;</p><p style="text-align: left;">typedef unsigned long long ll;</p><p style="text-align: left;">int n, m, map[81][81];</p><p style="text-align: left;">struct highNum</p><p style="text-align: left;">{</p><p style="text-align: left;"> ll num[maxnum];</p><p style="text-align: left;"> highNum(int length = 1)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> memset(num, 0, sizeof(num));</p><p style="text-align: left;"> num[0] = length;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> highNum operator = (highNum b)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> memcpy(num, b.num, sizeof(b.num));</p><p style="text-align: left;"> return *this;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> highNum operator = (int b)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> *this = highNum();</p><p style="text-align: left;"> num[num[0]] = b;</p><p style="text-align: left;"> return *this;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> bool operator < (const highNum& b) const</p><p style="text-align: left;"> {</p><p style="text-align: left;"> if(num[0] < b.num[0]) return true;</p><p style="text-align: left;"> if(num[0] == b.num[0])</p><p style="text-align: left;"> {</p><p style="text-align: left;"> for(int i = num[0]; i >= 1; --i)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> if(num[i] > b.num[i]) return false;</p><p style="text-align: left;"> if(num[i] < b.num[i]) return true;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;"> return false;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> highNum operator + (const highNum& b) const</p><p style="text-align: left;"> {</p><p style="text-align: left;"> highNum c = highNum(max(num[0], b.num[0]));</p><p style="text-align: left;"> for(int i = 1; i <= c.num[0]; ++i)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> c.num[i] += num[i] + b.num[i];</p><p style="text-align: left;"> c.num[i + 1] += c.num[i] / M;</p><p style="text-align: left;"> c.num[i] %= M;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> while(c.num[c.num[0] + 1] > 0)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> ++c.num[0];</p><p style="text-align: left;"> c.num[c.num[0] + 1] += c.num[c.num[0]] / M;</p><p style="text-align: left;"> c.num[c.num[0]] %= M; </p><p style="text-align: left;"> }</p><p style="text-align: left;"> return c;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> highNum operator * (const int b) const</p><p style="text-align: left;"> {</p><p style="text-align: left;"> highNum c = highNum(num[0]);</p><p style="text-align: left;"> for(int i = 1; i <= c.num[0]; ++i)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> c.num[i] += num[i] * b;</p><p style="text-align: left;"> c.num[i + 1] += c.num[i] / M;</p><p style="text-align: left;"> c.num[i] %= M;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> while(c.num[c.num[0] + 1] > 0)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> ++c.num[0];</p><p style="text-align: left;"> c.num[c.num[0] + 1] += c.num[c.num[0]] / M;</p><p style="text-align: left;"> c.num[c.num[0]] %= M;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> while(c.num[c.num[0]] == 0 && c.num[0] > 1) --c.num[0];</p><p style="text-align: left;"> return c;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> highNum operator * (const highNum& b) const</p><p style="text-align: left;"> {</p><p style="text-align: left;"> highNum c = highNum(num[0] + b.num[0]);</p><p style="text-align: left;"> for(int i = 1; i <= num[0]; ++i) for(int j = 1; j <= b.num[0]; ++j)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> c.num[i + j - 1] += num[i] * b.num[j];</p><p style="text-align: left;"> c.num[i + j] += c.num[i + j - 1] / M;</p><p style="text-align: left;"> c.num[i + j - 1] %= M;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> while(c.num[c.num[0] + 1] > 0)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> ++c.num[0];</p><p style="text-align: left;"> c.num[c.num[0] + 1] += c.num[c.num[0]] / M;</p><p style="text-align: left;"> c.num[c.num[0]] %= M;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> while(c.num[c.num[0]] == 0 && c.num[0] > 1) --c.num[0];</p><p style="text-align: left;"> return c;</p><p style="text-align: left;"> }</p><p style="text-align: left;">};</p><p style="text-align: left;">ostream& operator << (ostream& o, highNum& b)</p><p style="text-align: left;">{</p><p style="text-align: left;"> o << b.num[b.num[0]];</p><p style="text-align: left;"> o.setf(ios::fixed);</p><p style="text-align: left;"> o.width(8);</p><p style="text-align: left;"> o.fill('0');</p><p style="text-align: left;"> for(int i = b.num[0] - 1; i >= 1; --i) o << b.num[i];</p><p style="text-align: left;"> return o;</p><p style="text-align: left;">}</p><p style="text-align: left;">highNum ans, f[81][81], pw[81];</p><p style="text-align: left;">void init()</p><p style="text-align: left;">{</p><p style="text-align: left;"> cin >> n >> m;</p><p style="text-align: left;"> for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j)</p><p style="text-align: left;"> cin >> map[i][j];</p><p style="text-align: left;"> pw[1] = 2;</p><p style="text-align: left;"> for(int i = 2; i <= m; ++i) pw[i] = pw[i - 1] * 2;</p><p style="text-align: left;">}</p><p style="text-align: left;">void work(int row)</p><p style="text-align: left;">{</p><p style="text-align: left;"> for(int i = 1; i <= m; ++i) for(int j = 1; j <= m; ++j)</p><p style="text-align: left;"> f[i][j] = highNum();</p><p style="text-align: left;"> for(int i = 1; i <= m; ++i) f[i][i] = pw[m] * map[row][i];</p><p style="text-align: left;"> for(int p = 1; p < m; ++p) for(int i = 1; i <= m - p; ++i)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> int j = i + p;</p><p style="text-align: left;"> f[i][j] = max(f[i + 1][j] + pw[m - p] * map[row][i], f[i][j - 1] + pw[m - p] * map[row][j]);</p><p style="text-align: left;"> }</p><p style="text-align: left;"> ans = ans + f[1][m];</p><p style="text-align: left;">}</p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"> init();</p><p style="text-align: left;"> for(int i = 1; i <= n; ++i) work(i);</p><p style="text-align: left;"> cout << ans;</p><p style="text-align: left;"> return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。