小明和小红是两位魔法师，他们一起在一张N*N的方格地图上冒险（N<=9）去击败魔王，地图中的方格代表他们所走的路径，方格中的正整数代表可获得的法力值，而其他的方格中的数字为0代表无法获得法力值，如下图所示（见样例）：
他们二人从图上的起点出发，为了更快的打败魔王，他只能向右或者向下前进，直到到达下方的魔王城。在走过的路上，他们能够获得地图里的数字（获取后地图中将变为数字0）变为法力值。小明先从起点出发走到魔王城，然后小红再出发到达魔王城，为了更好的对抗魔王，请你帮帮2位魔法师使其获得的法力值为最大。
输入描述：
第一行为1个整数N(0<N<=9)表示N*N的地图，然后输入若干行，每行中有3个整数，前2个表示位置坐标x,y(1<=x,y<=N)，第3个数为该坐标提供的法力值k(0<=k<65536)。最后一行数输入单独的一行0 0 0表示输入结束。
输出描述：
只需要输出一个整数，表示小明和小红能获得的最大法力值的和。
样例1：
输入：
7
2 1 12
2 5 8
2 6 6
3 3 5
4 3 13
6 6 5
7 2 1
0 0 0
输出：
49
样例2：
输入：
5
1 1 5
1 3 6
2 5 6
4 2 13
5 1 5
0 0 0
输出：
30
动态规划
- 1、确定dp数组极其含义
dp[i][j]表示坐标为i,j的位置最大法力为dp[i][j]. - 2、确定递推公式
dp[i][j]可由两个方向进行得到，一个是dp[i-1][j],另一个是dp[i][j-1]，因为本题要获取最大法力，因此：dp[i][j]=max(dp[i-1][j],dp[i][j-1])+mp[i][j] - 3、如何初始化
因为只有两个方向，因此在边缘上对其进行累加即可。
完整cpp代码：
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<bits/stdc++.h>
using namespace std;
void my_dp(int N,vector<vector<int>> &dp, vector<vector<int>>& mp, vector<vector<int>>& mp_b)
{
for (int i = 1; i < N; i++)
{
for (int j = 1; j < N; j++)
{
int a = dp[i - 1][j];
int b = dp[i][j - 1];
if (a >= b) //选择向右的路径
{
dp[i][j] = a + mp[i][j]; // 计算此时的最大法力值
mp[i - 1][j] = 0; // 由题意，我们走了这个地方就需要将该点的法力值清0
for (int p = 0; p < j; p++)// 那么该点上面的数据我们需要将其保持恒定不变，从备份图中拷贝过来
mp[i][p] = mp_b[i][p];
}
else
{
dp[i][j] = b + mp[i][j];// 和上面一样
mp[i][j - 1] = 0;
for (int p = 0; p < i; p++)
mp[p][j] = mp_b[p][j];
}
}
}
}
void my_Init(int N,vector<vector<int>> &dp, vector<vector<int>> mp)
{
int tem = 0;
for (int i = 0; i < N; i++) // 进行初始化，因为只能向下和向右，因此边缘为边缘数据的累和
{
tem += mp[i][0];
dp[i][0] = tem;
}
tem = 0;
for (int i = 0; i < N; i++)
{
tem += mp[0][i];
dp[0][i] = tem;
}
}
int main() {
int N = 0;
cin >> N;
vector<vector<int>> mp(N,vector<int>(N,0));//构建地图
while (true) // 数据输入
{
int x, y, z;
cin >> x >> y >> z;
if (x == 0 && y == 0 && z == 0)
break;
mp[x-1][y-1] = z;
}
vector<vector<int>> mp_b = mp; // 进行地图备份
// dp[i][j] 表示位置在i和j处能获得的最大法力
// dp[i][j] = max(dp[i-1][j],dp[i][j-1])
// 创建dp数组
vector<vector<int>> dp(N,vector<int>(N,0));
vector<vector<int>> dp1(N, vector<int>(N, 0));
// 进行第一个人dp数组初始化
my_Init(N,dp,mp);
//进行第一个人dp
my_dp(N,dp,mp,mp_b);
mp[0][0] = 0;
mp[N - 1][N - 1] = 0; // 上面是从1,1点开始的，我们需要手动将起点和重点清0
// 第二轮开始，从新初始化dp1
my_Init(N, dp1, mp);
// 进行第二个人的dp
my_dp(N, dp1, mp, mp_b);
// 两人最大法力值为两个dp数组的和
cout << dp[N-1][N-1]+dp1[N-1][N-1] << endl;
}
