题解：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，需要写函数输出。

题目总结与参考代码

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

CPP

#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;
}

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

文章操作

题目分析

题目总结与参考代码

相关推荐

评论

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