【动态规划】JZOJ_6313 Maja

本文主要是介绍【动态规划】JZOJ_6313 Maja，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出一个$n\ast m$的矩阵，每个格子有些价值，走到这个格子可以获得$C_{i,j}$点，求从起点走k步并且回到起点(a,b)的最大价值。

思路

设$f_{k,i,j}$为$k$步时在点(i,j)获得的最大价值，40分转移显然。

可以发现一个性质，走的路是一条走过去，然后在两个点之间摩擦，再原路返回。

然后就可以优化dp。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};struct node {int x, y;long long k;
};
int n, m, a, b;
long long K, ans;
int c[101][101];
long long f[2][101][101];int main() {scanf("%d %d %d %d %d", &n, &m, &a, &b, &K);for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)scanf("%d", &c[i][j]);memset(f, -127, sizeof(f));f[0][a][b] = 0;K /= 2;for (int k = 1; k <= std::min(K, (long long)n * m); k++) {memset(f[k & 1], -127, sizeof(f[k & 1]));for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {long long &sb = f[k & 1][i][j];int t = 0;for (int z = 0; z < 4; z++) {int x = i + dx[z], y = j + dy[z];if (x < 1 || x > n || y < 1 || y > m || f[(k & 1) ^ 1][x][y] < 0) continue;sb = std::max(sb, f[(k & 1) ^ 1][x][y] + c[i][j]);t = std::max(t, c[x][y]);}if (sb < 0) continue;ans = std::max(ans, (sb + (t + c[i][j]) * ((K - k) / 2)) * 2 - c[i][j]);}}printf("%lld", ans);
}

这篇关于【动态规划】JZOJ_6313 Maja的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---