题解：P1005 [NOIP2007 提高组] 矩阵取数游戏

· · 题解

题目分析

本题每行独立，所以可以对每一行分别处理。对于每一行，其实就是区间动态规划。比较注意的是动态规划的顺序问题。

本题的区间动态规划中与以往不同的一点是，我们是从 dp_{1, n}（即最大区间）开始转移的。

对于一行 k，记 dp_{k, i, j} 为这一行还剩 [i, j] 未取的情况，所获得的最大得分，我们的转移方程是：

dp_{k, i, j} = \text{max}(dp_{k, i, j+1} + a_{k, j+1} \times 2 ^ {m - j + i - 1}, dp_{k, i-1, j} + a_{k, i-1} \times 2 ^ {m - j + i - 1})

此处需要特别注意：分数的倍率 2 ^ x 取决于取了多少个数，而不是目前转移区间的长度。取了多少数就是整个区间的长度减去目前转移区间的长度。

接下来我们分析转移。行号转移从 1 \to n 即可，左端点 l 也可以升序，但是列号右端点转移从 l \to m 就会出现取的值还没有算过的情况。我们可以将其逆转过来，即从 m \to l 就可以了。常见的方法有翻转循环顺序，调整两个循环的顺序。

最终统计答案时，每一个最小 1 区间都可能作为转移终点，我们需要对每一个最小区间求最终的答案，即最大值。

比较需要注意的一点是，本题常数较大，需要使用高精度。不过现在可以偷懒的办法是使用 __int128。但要注意，cout 无法直接输出 __int128，需要写函数输出。

题目总结与参考代码

本题是一个区间动态规划好题，要注意递推顺序与常数的问题带来的影响。

#include <bits/stdc++.h>
using namespace std;

int n, m, a[85][85];
__int128 dp[85][85][85], ans, k1 = 1;

void out(__int128 t){
    if (t > 9) out(t / 10);
    putchar(t % 10 + 48); 
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    for (int k = 1; k <= n; k++){
        for (int i = 1; i <= m; i++){
            for (int j = m; j >= i; j--){
                int len = j - i + 1;
                dp[k][i][j] = max(dp[k][i][j], dp[k][i][j+1] + a[k][j+1] * (k1 << m - len));
                dp[k][i][j] = max(dp[k][i][j], dp[k][i-1][j] + a[k][i-1] * (k1 << m - len));
            }
        }
    }
    for (int i = 1; i <= n; i++){
        __int128 mx = 0;
        for (int j = 1; j <= m; j++){
            mx = max(mx, dp[i][j][j] + a[i][j] * (k1 << m));
        }
        ans += mx;
    }
    out(ans);
    return 0;
}