Noip2007矩阵取数游戏题解

• 题目描述 Description
  【问题描述】
  帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的$n*m$的矩阵，矩阵中的每个元素$a_{i,j}$均
  为非负整数。游戏规则如下：

  1. 每次取数时须从每行各取走一个元素，共$n$个。$m$次后取完矩阵所有元素；
  2. 每次取走的各个元素只能是该元素所在行的行首或行尾；
  3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分$=$被取走的元素值$*2^i$，
     其中$i$表示第$i$ 次取数（从$1$ 开始编号）；
  4. 游戏结束总得分为$m$次取数得分之和。
     帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

• 输入描述 Input Description
  第1行为两个用空格隔开的整数$n$和$m$。
  第$2\sim 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*2^1+2*2^1=6$
  第2次：两行均取行首元素，本次得分为$2*2^2+3*2^2=20$
  第3次：得分为$3*2^3+4*2^3=56$。总得分为$6+20+56=82$
  【限制】
  $60\%$的数据满足：$1\le n, m\le 30$, 答案不超过$10^{16}$
  $100\%$的数据满足：$1\le n, m\le 80, 0\le a_{i,j}\le 1000$

• 题解
  可以看出每行是相互独立的，所以可以先考虑每一行。问题简化为每次可以取一列数的第一个或最后一个，第$i$次取数获得的得分是$a_i*2^i$，问取这一列数可获得的最大得分。
  这样就可以很显然地看出是区间dp了。
  用$f[i][j]$表示取完$[i,j]$里的数后所获得的最大得分，应有：
  $f[i][j]=max\{f[i+1][j]+a[i]*2^{m-j+i},f[i][j-1]+a[j]*2^{m-j+i}\}$
  即第一次取的是头上的元素和第一次取的是尾部的元素取最大值。
  然后$n$遍dp，把每行的最大值加起来就得到了答案。
  本题需要写高精。

• Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
const int maxnum = 35;
const int M = 100000000;            //压位到一亿
typedef unsigned long long ll;      //所以开long long
int 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;
}