Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

#P1004 方格取数

题目描述

设有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

##说明

NOIP 2000 提高组第四题

#分析

根据数据范围,显然不能采用搜索。

如果直接按照题目编写dp,显然具有后效性。在dp中无法记录走过的路径,更不可能把“走过的路径上的数变为0”,所以对于这样的问题,一般是采用多维dp,同时将路径选出。

为了方便,可以想象成有两个人,同时从起点出发,走到终点。

用dp[i][j][k][l]表示两人分别走到了(i,j)和(k,l)这两个点。

先不考虑走过的数变为0的情况,则dp[i][j][k][l]受到这四个状态的控制:

dp[i-1][j][k-1][l]

dp[i-1][j][k][l-1]

dp[i][j-1][k-1][l]

dp[i][j-1][k][l-1]

因为要取最大的数,可以得到状态转移方程如下

dp[i][j][k][l] = max{dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]} + a[i][j] + a[k][l];

下面可以考虑走过的数变为0这个要求了。

题目告诉我们,对于每次决策,必须且只有“向下走1格”和“向右走1格”这两种可能。

所以,无论在什么时候,两个人走到的点距离起点的曼哈顿距离都是一样的,即i+j=k+l

并且,对于一个点(i,j),从原点出发,无论怎么走,到这个点所经过的距离均为i+j

所以可以得知,当两个人选的路程有公共点时,两个人一定同时到达这个公共点。

所以只需在进行dp的时候,判断i,j是否等于k,l,如果等于,则在转移的时候只需加一遍这个格上的数即可。

#####即

dp[i][j][k][l] = max{dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]} + a[i][j];

则程序不难写出

#include <iostream>
using namespace std;
int map[15][15];
int dp[15][15][15][15];
int m;
int main()
{
    cin >> m;
    int x,y,n;
    do{
        cin >> x >> y >> n;
        map[x][y] = n;
    }while(x != 0 || y != 0 || n != 0);
    for(int i = 1;i <= m;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            for(int k = 1;k <= m;k++)
            {
                for(int l = 1;l <= m;l++)
                {
                    int ma1 = max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]);
                    int ma2 = max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]);
                    dp[i][j][k][l] = max(ma1,ma2)+map[i][j]+map[k][l];
                    if(i == k && j == l)
                    {
                        dp[i][j][k][l] -= map[i][j]; 
                    }
                }
            }
        }
    }
    cout << dp[m][m][m][m];
}

复杂度达到O(n^4) 尽管对于这个题目而言,这么高的复杂度也能AC,但是仍有简单有效的优化方法。

首先考虑复杂度这么高的原因

#####状态参数太多

对于所有状态,我们需要四个参数才能区分他们,这是很不必要的。

前面提到过i+j=k+l这个关系。

变形一下,可得到l=i+j-k

###!!!

也就是说,l这个参数可以通过前面三个参数推出来

那我还存他干什么

用dp[i][j][k]表示两人分别走到了(i,j)和(k,i+j-k)这两个点。

则状态转移方程为

dp[i][j][k] = max{dp[i-1][j][k-1],dp[i-1][j][k],dp[i][j-1][k-1],dp[i][j-1][k]} + a[i][j] + a[k][i+j-k];(i,j != k,l)

dp[i][j][k] = max{dp[i-1][j][k-1],dp[i-1][j][k],dp[i][j-1][k-1],dp[i][j-1][k]} + a[i][j];(i,j == k,l)

优化后的程序如下

    #include <iostream>
    using namespace std;
    int map[15][15];
    int dp[15][15][15];
    int m;
    int main()
    {
        cin >> m;
        int x,y,n;
        do{
            cin >> x >> y >> n;
            map[x][y] = n;
        }while(x != 0 || y != 0 || n != 0);
        for(int i = 1;i <= m;i++)
        {
            for(int j = 1;j <= m;j++)
            {
                for(int k = 1;k <= m;k++)
                {
                    int l = i + j - k;
                    int ma1 = max(dp[i-1][j][k-1],dp[i-1][j][k]);
                    int ma2 = max(dp[i][j-1][k-1],dp[i][j-1][k]);
                    dp[i][j][k] = max(ma1,ma2)+map[i][j]+map[k][l];
                    if(i == k && j == l)
                    {
                        dp[i][j][k] -= map[i][j]; 
                    }
                }
            }
        }
        cout << dp[m][m][m];
    }
复杂度O(n^3)

评论