P1004 [NOIP 2000 提高组] 方格取数
题目描述
设有 N×N 的方格图 (N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0。如下图所示（见样例）:
某人从图的左上角的 A 点出发，可以向下行走，也可以向右走，直到到达右下角的 B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 0）。
此人从 A 点到 B 点共走两次，试找出 2 条这样的路径，使得取得的数之和为最大。
输入格式
输入的第一行为一个整数 N（表示 N×N 的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的 0 表示输入结束。
输出格式
只需输出一个整数，表示 2 条路径上取得的最大的和。
输入输出样例
输入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0输出
67说明/提示
数据范围：1≤N≤9。
代码
无注释版
#include<bits/stdc++.h>
using namespace std;
int qq[20][20];
int pp[20][20][20][20];
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;int a,b,c;while(cin>>a>>b>>c&&a!=0&&b!=0&&c!=0){qq[a][b]=c;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int p=1;p<=n;p++){for(int q=1;q<=n;q++){pp[i][j][p][q]=max(pp[i-1][j][p][q-1],max(pp[i-1][j][p-1][q],max(pp[i][j-1][p][q-1],pp[i][j-1][p-1][q])))+qq[i][j]+qq[p][q];if(i==p&&j==q){pp[i][j][p][q]-=qq[i][j];}}}}}cout<<pp[n][n][n][n]<<"\n";
} 有注释版
#include<bits/stdc++.h> // 引入标准库，包含常用的C++库
using namespace std; // 使用标准命名空间int qq[20][20]; // qq[a][b]存储方格(a, b)上面的数值
int pp[20][20][20][20]; // pp[i][j][p][q]表示从(1, 1)到(i, j)的路径和与从(1, 1)到(p, q)的路径和（两个路径不能重叠）int main(){ios::sync_with_stdio(0); // 加速输入输出cin.tie(0); // 解绑cin和cout，提升效率cout.tie(0); // 解绑cin和cout，提升效率int n;cin >> n; // 输入方格的大小 Nint a, b, c;// 输入方格中的值，直到输入 0 0 0 为止while(cin >> a >> b >> c && a != 0 && b != 0 && c != 0) {qq[a][b] = c; // 在方格(a, b)中填入数字c}// 动态规划计算从(1, 1)到任意点(i, j)的路径和，以及从(1, 1)到任意点(p, q)的路径和for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {for(int p = 1; p <= n; p++) {for(int q = 1; q <= n; q++) {// 动态规划公式：更新pp[i][j][p][q]，即从(1, 1)到(i, j)和从(1, 1)到(p, q)的路径和pp[i][j][p][q] = max(pp[i-1][j][p][q-1], max(pp[i-1][j][p-1][q],max(pp[i][j-1][p][q-1], pp[i][j-1][p-1][q]))) + qq[i][j] + qq[p][q];// 如果路径(i, j)和(p, q)重叠，那么需要减去重复的方格值if(i == p && j == q) {pp[i][j][p][q] -= qq[i][j]; // 减去重复的格子值}}}}}// 输出从(1, 1)到(n, n)和从(1, 1)到(n, n)的路径和的最大值cout << pp[n][n][n][n] << "\n";
}