LuoGu P1005 矩阵取数游戏

题目链接

一道挺有意思的区间DP，写了一个下午，自己对DP的掌握确实还是太low了，其实想法很简单，可以发现每行怎么取并不会有什么影响，只要算出每行的最大取法，然后加起来就可以了。

故转移方程为 $f[i][j]=max(2f[i+1][j]+2a[i],2f[i][j-1]+2a[j])$

这里记录一下自己的误区，因为题目要求从两边开始取，自己就一直从两边开始进行dp，然后错了很长时间，最后发现其实经过简单的转换，他就会变成从内而外取数的方式，对从内而外的区间dp，参考回文串，我们只需要枚举区间长度和区间起始位置即可，这里我没有写高精度，因为对我而言最有意义的是dp的过程。

#define inf 0x3f3f3f3f
#define ll long long
#define vec vector<int>
#define P pair<int,int>
#define MAX 85ll n, m, a[MAX][MAX], dp[MAX][MAX][MAX];
//l,r:分别表示第i行矩阵从左数选过了第几个，从右数选过了第几个int main() {cin >> m >> n;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)cin >> a[i][j];memset(dp, 0, sizeof(dp));ll res = 0;for (int i = 1; i <= m; i++) {ll base = 2;for (int j = 1; j <= n; j++)dp[i][j][j] = base * a[i][j];for (int l = 2; l <= n; l++) {//区间长度for (int j = 1; j + l - 1 <= n; j++) {//枚举开始位置int t = j + l - 1;dp[i][j][t] = max(2 * dp[i][j + 1][t] + 2 * a[i][j], 2 * dp[i][j][t - 1] + 2 * a[i][t]);}base *= 2;}res += dp[i][1][n];}cout << res << endl;
}