题目描述
设有 N×N 的方格图 (N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0。如下图所示（见样例）:
某人从图的左上角的 A 点出发，可以向下行走，也可以向右走，直到到达右下角的 B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 0）。
此人从 A 点到 B 点共走两次，试找出 2 条这样的路径，使得取得的数之和为最大。
输入格式
输入的第一行为一个整数 N（表示 N×N 的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的 0 表示输入结束。
输出格式
只需输出一个整数，表示 2 条路径上取得的最大的和。
输入输出样例
输入 #1复制
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
输出 #1复制
67
说明/提示
数据范围：1≤N≤9。
题解：
看着很简单的一道题，数据范围也很小，这多美好啊是吧。
看完题，因为知道是动态规划的题就直接上了一个一维的DP，DP[i]来记录到maps[i][i]的最大的和，就是一条支路的最优解，然后再通过记录的路线，更改原始maps，然后再DP一遍就好了。看着挺不错的，但是问题就出在这。一次最优不一定二次最优，这个方法使用了贪心的策略，所以很可惜，最后有两个样例过不了。
后来改了几个方案，但是最多只有二维的DP，所以还是过不了。
偷偷看了一眼题解，发现原来是要用四维的DP，其中DP[i][j][k][h]是到[i][j]的第一条路和到[k][h]的第二条路的和，及题目的答案。有点难想到。
状态转移方程：
要注意当i==k，j==h的时候多加了一格要减去。
令外说一句，这题回溯法更简单。
代码：
一维/二维+贪心代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<set>
using namespace std;
typedef long long int ll;
int n=0,i,j,k;
vector<vector<int>> maps(101,vector<int>(101,0));
int x=0,y=0,num=0;
vector<int> dp(101,0);
vector<vector<int>> road(101,vector<int>(101,0));
int ans=0;
int main(){
cin >> n;
while(true){
cin >> x >> y >> num;
if(x==0 && y==0 && num==0){
break;
}
maps[x][y]=num;
}
dp[1]=maps[1][1];
for(i=2;i<=n;i++){
int t=0,t1=0,t2=0,maxt=0;
for(j=1;j<i;j++){
t1=dp[j];
t2=dp[j];
for(k=j+1;k<=i;k++){
t1+=maps[k][j];
t1+=maps[i][k];
t2+=maps[j][k];
t2+=maps[k][i];
}
t=max(t1,t2);
//cout << t1 << " " << t2 << "\n";
if(maxt<=t){
road[i][0]=j;
if(t1>=t2){
road[i][1]=1;
}
else{
road[i][1]=2;
}
}
maxt=max(maxt,t);
}
dp[i]=maxt;
}
ans=dp[n];
//cout << ans << "\n";
/*
for(i=1;i<=n;i++){
cout << road[i][0] << " " << road[i][1] << "\n";
}
*/
if(n==1){
cout << ans << "\n";
return 0;
}
int nn=n;
while(nn!=1){
int t1=road[nn][0];
int t2=road[nn][1];
if(t2==1){
for(i=t1;i<=nn;i++){
maps[i][t1]=0;
maps[nn][i]=0;
}
}
else if(t2==2){
for(i=t1;i<=nn;i++){
maps[t1][i]=0;
maps[i][nn]=0;
}
}
nn=t1;
}
/*
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
cout << maps[i][j] << " ";
}
cout << "\n";
}
*/
dp[1]=maps[1][1];
for(i=2;i<=n;i++){
int t=0,t1=0,t2=0,maxt=0;
for(j=1;j<i;j++){
t1=dp[j];
t2=dp[j];
for(k=j+1;k<=i;k++){
t1+=maps[k][j];
t1+=maps[i][k];
t2+=maps[j][k];
t2+=maps[k][i];
}
t=max(t1,t2);
maxt=max(maxt,t);
}
dp[i]=maxt;
}
ans+=dp[n];
cout << ans << "\n";
return 0;
}四维DP代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<set>
using namespace std;
typedef long long int ll;
int n=0,i,j,k,h;
vector<vector<int>> maps(101,vector<int>(101,0));
int x=0,y=0,num=0;
int ans=0;
int dp[101][101][101][101];
int main(){
cin >> n;
while(true){
cin >> x >> y >> num;
if(x==0 && y==0 && num==0){
break;
}
maps[x][y]=num;
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
for(k=1;k<=n;k++){
for(h=1;h<=n;h++){
int t1=max(dp[i-1][j][k-1][h],dp[i-1][j][k][h-1]);
int t2=max(dp[i][j-1][k-1][h],dp[i][j-1][k][h-1]);
dp[i][j][k][h]=max(t1,t2)+maps[i][j]+maps[k][h];
if(i==k && j==h){
dp[i][j][k][h]-=maps[i][j];
}
}
}
}
}
cout << dp[n][n][n][n] << "\n";
return 0;
}
标签：vector,101,NOIP2000,int,P1004,取数,num,include,DP From： https://blog.csdn.net/2301_78848414/article/details/144347886