NOIP2000提高組複賽 方格取數 解題報告

題四． 方格取數

問題描述

設有N*N的方格圖(N<=10,我們將其中的某些方格中填入正整數,而其他的方格中則放入數字0。如下圖所示（見樣例）：

                                       向右

      A  1    2    3   4    5    6    7    8

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

向

下

某人從圖的左上角的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

【分析】

簡單動態規劃，DP兩條路徑即可。

 狀態設定：F[i][j][k][m]表示走到(i,j),(k,m)取的數的最大值。

                  mat[i][j]表示方格(i,j)裡的數。

狀態轉移方程： F[i][j][k][m]=max{F[i-1][j][k-1][m],F[i-1][j][k][m-1],F[i][j-1][k-1][m],F[i][j-1][k][m-1]}+A  （其中A的取值：如果i!=k || j!=m,A=mat[i][j]+mat[k][m];如果i==k&&j==m,A=mat[k][m]）

 目標狀態：F[N][N][N][N]

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int mat[11][11];
int F[11][11][11][11];
int N;

int Max(int a,int b,int c,int d)
{
    if(b>a)
        a=b;
    if(c>a)
        a=c;
    if(d>a)
        a=d;
    return a;
}

void init()
{
    cin>>N;
    int a,b,c;
    cin>>a>>b>>c;
    while (a!=0 || b!=0 ||c!=0)
    {
        mat[a][b]=c;
        cin>>a>>b>>c;
    }

    return;   
}

void dp()
{
    for (int i=1;i<=N;i++)
    {
        for (int j=1;j<=N;j++)
        {
            for (int k=1;k<=N;k++)
            {
                for (int m=1;m<=N;m++)
                {
                    if(i==k && j==m)
                    {
                        F[i][j][k][m]=Max(F[i-1][j][k-1][m],F[i-1][j][k][m-1],
                    F[i][j-1][k-1][m],F[i][j-1][k][m-1])+mat[k][m];
                        continue;
                    }
                    F[i][j][k][m]=Max(F[i-1][j][k-1][m],F[i-1][j][k][m-1],
                    F[i][j-1][k-1][m],F[i][j-1][k][m-1])+mat[i][j]+mat[k][m];
                }
            }
        }
    }
    cout<<F[N][N][N][N]<<endl;
}

int main()
{
    freopen("fgqs.in","r",stdin);
    freopen("fgqs.out","w",stdout);
    init();
    dp();
    return 0;
}