洛谷千题详解 | P1004 [NOIP2000 提高组] 方格取数【C++、Java、Pascal语言】

博主主页：Yu·仙笙

 

专栏地址：洛谷千题详解

目录

题目描述

输入格式

输出格式

输入输出样例

解析： 

C++源码： 

Java源码： 

Pascal源码：

---

-------------------------------------------------------------------------------------------------------------------------------  

-------------------------------------------------------------------------------------------------------------------------------  

题目描述

设有 N×N 的方格图 (N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0。如下图所示（见样例）:

A
 0  0  0  0  0  0  0  0
 0  0 13  0  0  6  0  0
 0  0  0  0  7  0  0  0
 0  0  0 14  0  0  0  0
 0 21  0  0  0  4  0  0
 0  0 15  0  0  0  0  0
 0 14  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
                         B

某人从图的左上角的 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、两种都向下走

2、第一种向下走，第二种向右走

3、第一种向右走，第二种向下走

4、两种都向右走

每走一步走枚举一下这四种情况，因为在每个点的方案具有唯一性（也就是在某个点走到终点的取数方案只有一个最优解，自己理解一下），所以我们可以开一个数组来记录每一种情况，当重复枚举到一种情况时就直接返回（对，就是剪枝），大大节省了时间（不然会超时哦~）。深搜和动归的时间复杂度时一样的！

-------------------------------------------------------------------------------------------------------------------------------  

C++源码： 

#include
#include
using namespace std;
struct point
{
    int x,y,data;//记录每个点的位置和数值
}p[100];
int n,m,map[11][11],f[11][11];
int main()
{
    int i,ii,j,jj,l;
    scanf("%d",&n);
    while(1)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(!a&&!b&&!c)
            break;
        p[++m].x=a;
        p[m].y=b;
        p[m].data=c;
    }
    for(i=1;i<=m;i++)
        map[p[i].x][p[i].y]=p[i].data;
    for(l=2;l<=n*2;l++)//每个点最少横着竖着都走一格，最多都走n格就到终点
        for(i=l-1;i>=1;i--)//和前面说的一样，倒着做
            for(ii=l-1;ii>=1;ii--)
            {
                j=l-i;jj=l-ii;//i+j=ii+jj=l
                f[i][ii]=max(max(f[i][ii],f[i-1][ii-1]),max(f[i-1][ii],f[i][ii-1]))+map[i][j];
//重点说明一下吧，这里省略了很多。如果i不减1，意思就是j-1，因为上一个阶段就是l-1嘛。如果ii-1，意思就是说jj不减1。
                f[i][ii]+=map[ii][jj]*(i!=ii);
//如果i==ii，其实就是(i==ii&&j==jj)，因为和都是l嘛。如果走过一遍，第二遍走得到的值就是0（题目上说的）。
            }
    printf("%d\n",f[n][n]);
//输出意思是在路径长度为2*n的阶段，两遍都走到(n,n)的最优值。因为在这里(j=2*n-i=n,jj=2*n-ii=n),所以走到的就是(n,n)的位置
    return 0;

-------------------------------------------------------------------------------------------------------------------------------  

Java源码： 

import java.util.Scanner;
 
public class Main{
     public static void main(String[] args) {
         Scanner reade=new Scanner(System.in);
         int n=reade.nextInt();
         int [][]num=new int[n+1][n+1];
         while (true) {
             int x = reade.nextInt();
             int y = reade.nextInt();
             int total = reade.nextInt();
             if (x == 0 && y == 0 && total == 0)
                 break;
             num[x][y] = total;
         }
         int [][][][]f=new int[10][10][10][10];
         for (int x1 = 1; x1 <= n; x1++) {
             for (int y1 = 1; y1 <= n; y1++) {
                 for (int x2 = 1; x2 <= n; x2++) {
                     for (int y2 = 1; y2 <= n; y2++) {
 
                         f[x1][y1][x2][y2] = Math.max(
                                 Math.max(f[x1 - 1][y1][x2 - 1][y2], f[x1 - 1][y1][x2][y2 - 1]),
                                 Math.max(f[x1][y1 - 1][x2 - 1][y2], f[x1][y1 - 1][x2][y2 - 1]));
                         f[x1][y1][x2][y2] += num[x1][y1];
                         if ( x1 !=x2 && y1 != y2) {
                             f[x1][y1][x2][y2] += num[x2][y2];
                         }
                     }
                 }
             }
         }
         System.out.println(f[n][n][n][n]);
 
 
     }
 
 
 }

-------------------------------------------------------------------------------------------------------------------------------  

Pascal源码：

var n,m,i,j,l,p,x,y,o:longint;
     fl:array[0..100] of array[0..100] of longint;  //棋盘
     board:array[-2..51] of array[-2..51] of array[-2..51] of array[-2..51] of longint;   
   function canread:boolean;
     begin
     canread:=false;
     if (x<>0)and(y<>0)and(o<>0) then canread:=true;
     exit; 
     end;
     begin
     readln(n);
     m:=n;
     readln(x,y,o);
     while canread do
     begin
     fl[x,y]:=o; readln(x,y,o);
     end;
     for i:=1 to m do  
     for j:=1 to n do
     for l:=1 to m do
     for p:=1 to n do {**枚举**两条路分别走到的位置}
     begin
     if board[i-1,j,l-1,p]>board[i,j,l,p] then board[i,j,l,p]:=board[i-1,j,l-1,p];         //上上
     if board[i-1,j,l,p-1]>board[i,j,l,p] then board[i,j,l,p]:=board[i-1,j,l,p-1];         //左上
 if board[i,j-1,l-1,p]>board[i,j,l,p] then board[i,j,l,p]:=board[i,j-1,l-1,p];        //左左
 if board[i,j-1,l,p-1]>board[i,j,l,p] then board[i,j,l,p]:=board[i,j-1,l,p-1];        //上左
 
 
 
 
     inc(board[i,j,l,p],fl[i,j]);    //加上该点的值
     if (i<>l)and(j<>p) then inc(board[i,j,l,p],fl[l,p]);       //second
     end;
     writeln(board[m,n,m,n]);
     end.
 
 

 -------------------------------------------------------------------------------------------------------------------------------