题解 | 方格取数-NOIP2000提高组复赛D题
方格取数
https://ac.nowcoder.com/acm/contest/248/D
题目描述
设有
的方格图(N ≤ 10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示(见样例)：
某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
此人从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
输出
67
解答
这道题特点是要解题时同时顾及两个人
一个一个人地贪心肯定是行不通的
本题正解应该是dp，因为要同时考虑到两个人
于是设状态为第一个人在
，第二个人在
时能达到的最大答案
用
表示格子)
上的数字,%5C%20and%20%5C%20(y1%3D%3Dy2))
;
状态转移:
1.两个人同时向右走：
%3B)
1.两个人同时向右走：
2.两个人同时向下走：
%3B)
3.两个人分别向右和向下走
%3B)
4.两个人分别向下和向右走
%3B)
由于状态总共有n^4种，转移是常数，所以时间复杂度为%E2%80%8B)
有没有更好的方法呢？可以看出
换种说法，每个状态的两个人总是在同一条对角线上
于是可以枚举对角线，
设状态
状态转移与之前类似
由于对角线只有
于是时间复杂度缩减为
下面贴优化后代码
#include<cstdio>
int max(int a,int b){return a<b?b:a;}
int min(int a,int b){return a>b?b:a;}
int n;
int f[24][12][12];
int g[12][12];
int main(){
scanf("%d",&n);
int ag1,ag2,ag3;
while(scanf("%d%d%d",&ag1,&ag2,&ag3)&&ag1&&ag2&&ag3)
g[ag1][ag2]=ag3;
int lmt=n*2;
f[2][1][1]=g[1][1];
for(int i=3;i<=lmt;i++){
int c=min(i,n+1);
int s=i>n?i-n:1;
for(int j=s;j<c;j++)
for(int k=s;k<c;k++){
int x1=j,x2=k,y1=i-j,y2=i-k;
bool b=(x1==x2&&y1==y2);
int tmp=max(max(f[i-1][x1-1][x2-1],f[i-1][x1][x2]),
max(f[i-1][x1-1][x2],f[i-1][x1][x2-1]));
f[i][x1][x2]=max(f[i][x1][x2],tmp+g[x1][y1]+(b?0:g[x2][y2]));
//多加了个括号就对了！
//printf("f[%d][%d][%d]:%d,tmp:%d\n",i,x1,x2,f[i][x1][x2],tmp);
//getchar();
}
}
printf("%d\n",f[lmt][n][n]);
} 来源：Hineven
投递OPPO等公司10个岗位 >
