本文主要是介绍一般DP-双调取数问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stack>
#include <queue>
#include <set>
#include <math.h>
#include <time.h>/*=======================================
双调取数问题
从A -> B只能向下或者向右走，获取最大值dp[i][j]表示从(0, 0) -> (i, j)可以获取的最大值dp[i][j][m][n] = max(dp[i][j - 1][m][n - 1], dp[i - 1][j][m - 1][n], dp[i - 1][j][m][n - 1], dp[i][j - 1][m - 1][n]) + w[i][j];========================================*/
#define flush(arr, i) memset(arr, i, sizeof(arr))
typedef long long int64;
using namespace std;
const int MAX_ITEM = 20;
const int oo = 0x7fffffff;
//const int oo = 0x3f3f3f3f;int dp[MAX_ITEM][MAX_ITEM][MAX_ITEM][MAX_ITEM], w[MAX_ITEM][MAX_ITEM];int DP(int lx, int ly, int rx, int ry)
{if(lx <= 0 || ly <= 0 || rx <= 0 || ry <= 0)return 0;if(dp[lx][ly][rx][ry])return dp[lx][ly][rx][ry];int ans = max(max(DP(lx, ly - 1, rx, ry - 1), DP(lx - 1, ly, rx - 1, ry)), max(DP(lx, ly - 1, rx - 1, ry), DP(lx - 1, ly, rx, ry - 1)));if(lx == rx && ly == ry)ans += w[lx][ly];elseans = ans + w[lx][ly] + w[rx][ry];return dp[lx][ly][rx][ry] = ans;
}int main()
{freopen("0-data.txt", "r", stdin);int n, x, y, val;while(scanf("%d", &n) != EOF){flush(w, 0), flush(dp, 0);while(true){scanf("%d%d%d", &x, &y, &val);if(x + y + val == 0)break;w[x][y] = val;}printf("%d\n", DP(n - 1, n - 1, n - 1, n - 1));}return 0;
}
下面是简化的独立取数问题
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stack>
#include <queue>
#include <set>
#include <math.h>
#include <time.h>/*=======================================
取数问题
从A -> B只能向下或者向右走，获取最大值dp[i][j]表示从(0, 0) -> (i, j)可以获取的最大值dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + w[i][j];========================================*/
#define flush(arr, i) memset(arr, i, sizeof(arr))
typedef long long int64;
using namespace std;
const int MAX_ITEM = 110;
const int oo = 0x7fffffff;
//const int oo = 0x3f3f3f3f;int dp[MAX_ITEM][MAX_ITEM], w[MAX_ITEM][MAX_ITEM];int DP(int x, int y)
{if(x <= 0 || y <= 0)return 0;if(dp[x][y])return dp[x][y];return dp[x][y] = max(DP(x, y - 1), DP(x - 1, y)) + w[x][y];
}int main()
{freopen("0-data.txt", "r", stdin);int n, x, y, val;while(scanf("%d", &n) != EOF){flush(w, 0), flush(dp, 0);while(true){scanf("%d%d%d", &x, &y, &val);if(x + y + val == 0)break;w[x][y] = val;}printf("%d\n", DP(n - 1, n - 1));}return 0;
}
这篇关于一般DP-双调取数问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
