NOIP2000-S-4-方格取数 Runtime Error
0 分
*题目描述：
设有
N
∗
N
N∗N的方格图
(
N
<
1000
)
(N<=1000),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字
0
0。
某人从图的左上角的
A
A 点
(
1
,
1
)
(1,1)出发，可以向下行走，也可以向右走，直到到达右下角的
B
B点
(
N
,
N
)
(N,N)。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字
0
0）。
此人从
A
A点到
B
B 点，试找出
1
1条这样的路径，使得取得的数之和为最大。
例如:
8PpqgacUeXnY4AAAAASUVORK5CYII=
输入格式：
第一行为一个整数
N
(
N
≤
1000
)
N(N≤1000)，表示
N
×
N
N×N的方格图。
接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。一行
“
000
”
“000”表示结束。
输出格式：
第一个整数，表示一条路径上取得的最大的和。
样例输入：
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
样例输出：
36
时间：1s 空间：256M*
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int dp[N][N][N][N];
int w[1005][1005];
int n;
int max1(int a,int b,int c,int d)
{
int max2;
max2=max(a,b);
max2=max(max2,c);
max2=max(max2,d);
return max2;
}
int main(int argc, char** argv)
{
int a, b ,c;
cin>>n;
do
{
cin>>a>>b>>c;
w[a][b] = c;
}while(a&&b&&c);
for(int i1 = 1; i1 <= n; i1++)
for(int j1 = 1; j1 <= n; j1++)
for(int i2 = 1; i2 <= n; i2++)
for(int j2 = 1; j2 <= n; j2++)
{
//这里分别取四个状态的最大值
dp[i1][j1][i2][j2] =
max1(dp[i1-1][j1][i2-1][j2],dp[i1-1][j1][i2][j2-1],dp[i1][j1-1][i2-1][j2],dp[i1][j1-1][i2][j2-1]);
//如果走的重复的话
if(i1 == i2 && j1 == j2)
{
dp[i1][j1][i2][j2] += w[i1][j1];
}
else
{
dp[i1][j1][i2][j2] += w[i1][j1] + w[i2][j2];
}
}
cout<<dp[n][n][n][n]<<endl;
return 0;
}