闲话

这是我最后一个洛谷区间 dp 题单里还没做完的题了。好耶！一个题单又绿了。

题目大意

对于一个给定的 $n \times m$ 的矩阵，矩阵中的每个元素 $a_{i,j}$ 均为非负整数。游戏规则如下：

1. 每次取数时须从每行各取走一个元素，共 $n$ 个。经过 $m$ 次后取完矩阵内所有元素；
2. 每次取走的各个元素只能是该元素所在行的行首或行尾；
3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 $\times 2^i$，其中 $i$ 表示第 $i$ 次取数（从 $1$ 开始编号）；
4. 游戏结束总得分为 $m$ 次取数得分之和。

求取数后的最大得分。

对于 $100\%$ 的数据，满足 $1\le n,m\le 80$，$0\le a_{i,j}\le1000$。

思路

首先看到这题，一个二维的数组怎么也跟区间 dp 联系不到一块儿啊，看着更像是线性 dp。但是，仔细读题后可以发现，每一行之前并无关联，所以完全可以拆成 $n$ 个一维，上下之前不用处理。那么就可以往区间 dp 想了。之后做 $n$ 次区间 dp 即可。

由于本题没有多种情况，所以可以直接尝试定义 $dp[l][r]$ 为 dp 数组。 之后考虑转移。由于从边缘过来，那么就不用考虑合并了，直接从 $l-1$ 和 $r+1$ 转移即可。

之后想一下 $2^i$ 的 $i$ 是多少。由于已经取完了 $(r+1,m]$ 和 $[1,l-1)$ 的位置，那么当前位置就是 $m-r+l-1$ 了，也就是走到了 $l-1$ 和 $r+1$ 的位置。

那么总结一下吧：

$dp[l][r]=\max(dp[l-1][r]+2^{m-r+l-1}\times a[l-1],dp[l][r+1]+2^{m-r+l-1}\times a[r+1])$

所以最后枚举剩下的一个也就是 $dp[l][l]$，这个没有在之前处理次幂，只是从旁边的过来。所以要加上 $2^m\times a[l]$。

由于本题 $n,m\leq 80$，所以开 int128 或者用高精度处理一下即可。

代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MAXN=85;
typedef __int128 int128;
void write(int128 x){
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
}
ll n,m,a[MAXN];
int128 dp[MAXN][MAXN],two[MAXN],ans;
void init(){
    two[0]=1;
    for (int i = 1; i <85 ; ++i) {
        two[i]=two[i-1]*2;
    }
}
int main() {
    init();
    scanf("%lld%lld",&n,&m);
    for (int i = 1; i <=n ; ++i) {
        for (int j = 1; j <=m ; ++j) {
            for (int k = 1; k <=m ; ++k) {
                dp[j][k]=-two[84];
            }
        }
        for (int j = 1; j <=m ; ++j) {
            scanf("%lld",&a[j]);
        }
        for (int l = 1; l <=m ; ++l) {
            for (ll r = m; r >=l ; --r) {
                dp[l][r]= max(dp[l-1][r]+two[m-r+l-1]*a[l-1],dp[l][r+1]+two[m-r+l-1]*a[r+1]);
            }
        }
        int128 Max=-two[84];
        for (int j = 1; j <=m ; ++j) {
            Max= max(Max,dp[j][j]+two[m]*int128(a[j]));
        }
        ans+=Max;
    }
    write(ans);
    return 0;
}

总结

分析了在第一眼是二维的情况下可能会出现行与行之间没有联系，那么就是 $n$ 个一维而不是二维。就可以多考虑考虑区间 dp 了。

之后循环的顺序也可以从初始状态开始往一个方向走。如本题就是 $[1,m],[m,l]$ 的方法走的。