简答题 偏难
#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 &lt;cstdio&gt;</p><p style="text-align: left;">#include &lt;cstring&gt;</p><p style="text-align: left;">#include &lt;algorithm&gt;</p><p style="text-align: left;">#include &lt;iostream&gt;</p><p style="text-align: left;">#include &lt;iomanip&gt;</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 &lt; (const highNum&amp; b) const</p><p style="text-align: left;">    {</p><p style="text-align: left;">        if(num[0] &lt; 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 &gt;= 1; --i)</p><p style="text-align: left;">            {</p><p style="text-align: left;">                if(num[i] &gt; b.num[i]) return false;</p><p style="text-align: left;">                if(num[i] &lt; 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&amp; 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 &lt;= 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] &gt; 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 &lt;= 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] &gt; 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 &amp;&amp; c.num[0] &gt; 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&amp; 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 &lt;= num[0]; ++i) for(int j = 1; j &lt;= 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] &gt; 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 &amp;&amp; c.num[0] &gt; 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&amp; operator &lt;&lt; (ostream&amp; o, highNum&amp; b)</p><p style="text-align: left;">{</p><p style="text-align: left;">    o &lt;&lt; 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 &gt;= 1; --i) o &lt;&lt; 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 &gt;&gt; n &gt;&gt; m;</p><p style="text-align: left;">    for(int i = 1; i &lt;= n; ++i) for(int j = 1; j &lt;= m; ++j)</p><p style="text-align: left;">        cin &gt;&gt; map[i][j];</p><p style="text-align: left;">    pw[1] = 2;</p><p style="text-align: left;">    for(int i = 2; i &lt;= 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 &lt;= m; ++i) for(int j = 1; j &lt;= m; ++j)</p><p style="text-align: left;">        f[i][j] = highNum();</p><p style="text-align: left;">    for(int i = 1; i &lt;= m; ++i) f[i][i] = pw[m] * map[row][i];</p><p style="text-align: left;">    for(int p = 1; p &lt; m; ++p) for(int i = 1; i &lt;= 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 &lt;= n; ++i) work(i);</p><p style="text-align: left;">    cout &lt;&lt; ans;</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。