动态规划

题意：

设有NN的方格图(N ≤ 10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示(见样例)：

某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输入描述:
输入的第一行为一个整数N(表示NN的方格图)，接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
输出描述:
只需输出一个整数，表示2条路径上取得的最大的和。

分析:

动态规划，多重数组问题。要大胆加数组的维数，把所有的约束条件都给摆在明面上。并且题目所给的数据范围也有所提示！！

代码如下

#include<iostream>
#include<algorithm>
using namespace std;
const int max_n = 15;
int n;
int dp[max_n][max_n][max_n][max_n];
int in[max_n][max_n];

int main() {
    ios::sync_with_stdio(0);cin >> n;
    int x, y, val;
    while ((cin >> x >> y >> val) && !(x == 0 && y == 0 && val == 0))in[x][y] = val;
    dp[1][1][1][1] = in[1][1];
    for (int i = 1;i <= n;i++)
    for (int j = 1;j <= n;j++)
    for (int k = 1;k <= n;k++)
    for (int m = 1;m <= n;m++){
        if (i + j != k + m) continue;
        int tmp = in[i][j] + in[k][m];if (i == k && j == m)tmp -= in[i][j];
        dp[i][j][k][m] = max(dp[i][j][k][m], dp[i - 1][j][k - 1][m] + tmp);
        dp[i][j][k][m] = max(dp[i][j][k][m], dp[i - 1][j][k][m - 1] + tmp);
        dp[i][j][k][m] = max(dp[i][j][k][m], dp[i][j - 1][k - 1][m] + tmp);
        dp[i][j][k][m] = max(dp[i][j][k][m], dp[i][j - 1][k][m - 1] + tmp);
    }cout << dp[n][n][n][n] << endl;
}

注意的是：

if (i + j != k + m) continue;

这里，我们判断了一个明显不符合实际问题的条件！！！！
本题中或许并无大用，但是在记忆化搜索或许可能成为剪枝的切入口。对于信息的提取分析要敏锐

方格取数

动态规划

题意：

分析:

代码如下

注意的是：