[動態規劃]BYVoid魔獸世界模擬題: 艾薩拉的激流 azshara 解題報告

      艾薩拉的激流  azshara
問題描述

沿着卡利姆多北方邊界延展的破碎的海岸，在世界大分裂之前曾經 是暗夜精靈首都艾薩琳的一部分，艾薩拉。惡魔終於從這個世界被消除，這片土地被撕碎並被大海吞沒，剩下的只有曾經雄偉城市的廢墟。自那以後，這個岩石交錯 的島嶼、峭壁懸崖和珊瑚叢生的海洋成爲許多傳說來源。暗夜精靈們認爲這是個被詛咒的地方，從來沒有人敢來探險，連經驗最豐富的船長都從這裏繞行。因爲這裏 有巨大的水生物，可怕的暗礁，強大的激流與巨浪。然而傳聞這裏水下有着驚人的寶藏，一直吸引着地精們。

地精菲利克斯購買了最好的探險艇，來探索艾薩拉海岸水下傳說中的寶藏。不出所料，海底果然有大量的寶藏。但是這些寶藏被一個激流覆蓋，菲利克斯不可能把他的探險艇停下來。這個激流可以被描述爲一個W×L的矩形，分成個一個個單元格。每個單元格可能是寶藏，也可能是一塊礁石。從上遊開始，每過1秒， 菲利克斯的探險艇就會被衝往下游的一個單位。在被衝往下游的過程中，菲利克斯可以控制方向，選擇他的正前，左邊，或右邊的一個單位，以免觸碰礁石。菲利克 斯從這個激流的最上游的任意一個單元格開始向下漂流，每經過一個單元格就可以取走這個單元格上的寶藏。菲利克斯千萬不能碰到礁石，否則他的探險艇會損壞。 請你算出，菲利克斯最多一共能拿到多少個單位的寶藏。

輸入格式

第一行，兩個整數W，L。

接下來的L行，每行W個整數，以”從上游到下游，面朝水流方向從左向右“的順序依次爲每個單元格中的寶藏的單位數目，如果爲-1則表示這個單元格是礁石。

輸出格式

一個整數，表示得到的寶藏。

數據規模

1<=W<=1000

1<=L<=10000

所有涉及到的數字不會超過32位帶符號整型的範圍

樣例輸入

3 5

5 1 3

-1 7 -1

5 1 10

4 -1 7

20 10 5

樣例輸出

41

樣例說明

上游->下游	1	2	3	4	5
1	5	-1	5	4	20
2	1	7	1	-1	10
3	3	-1	10	7	5

如上表，菲利克斯可以從(1,1)開始，第1秒向右轉一下，被衝到(2,2)。第2秒向左轉一下，被衝到(3,1)。接下來正前行走，經過(4,1),(5,1)，一共拿到5+7+5+4+20=41個單位的寶藏。

本文由BYVoid大牛開發的開源的中文轉換引擎——Opencc翻譯。

(話說 我用BYVoid開發的翻譯引擎 翻譯BYVoid出的題目。。大牛啊！)

【分析】

簡單的動態規劃題目。

用mat[i][j]表示讀入的那個矩陣。

mat[i][j]=Max{mat[i-1][j-1],mat[i][j-1],mat[i+1][j-1]}+mat[i][j]

目標狀態：

   Max{mat[i][L]}

注意-1的判斷即可。

【我的代碼】

#include <iostream>
#include <cstdlib>
#include <cstdio>
#define Max(a,b) a>=b?a:b;
using namespace std;

int W,L;
int mat[1002][10002];
int M=0;

void init()
{
    scanf("%d %d\n",&W,&L);
    for (int i=1;i<=L;i++)
        for (int j=1;j<=W;j++)
            scanf("%d",&mat[j][i]);
}

void print()
{
    for (int i=1;i<=W;i++)
    {
        for (int j=1;j<=L;j++)
            cout<<mat[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
}

void dp()
{
    int tmp;
    for (int i=2;i<=L;i++)
    {
        for (int j=1;j<=W;j++)
        {
            if(mat[j][i]==-1)
                continue;
            tmp=0;
            if(j-1>=1 && mat[j-1][i-1]!=-1)
                tmp=Max(tmp,mat[j-1][i-1]);
           
            if(mat[j][i-1]!=-1)
                tmp=Max(tmp,mat[j][i-1]);
           
            if(j+1<=W && mat[j+1][i-1]!=-1)
                tmp=Max(tmp,mat[j+1][i-1]);
            mat[j][i]+=tmp;
            //if(mat[j][i]>M)
                //M=mat[j][i];
        }
    }
}

int main()
{
    freopen("azshara.in","r",stdin);
    freopen("azshara.out","w",stdout);
    init();
//    print();
    dp();
    //print();
    //int M=0;
    for (int i=1;i<=W;i++) 
        M=Max(M,mat[i][L]); 
    cout<<M<<endl;
    return 0;
}

【測評結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	39421 KB	0
2	正确	10	0.579 s	39421 KB	0
3	正确	10	0.000 s	39421 KB	0
4	正确	10	0.000 s	39421 KB	0
5	正确	10	0.014 s	39421 KB	0
6	正确	10	0.572 s	39421 KB	0
7	正确	10	0.572 s	39421 KB	0
8	正确	10	0.570 s	39421 KB	0
9	正确	10	0.567 s	39421 KB	0
10	正确	10	0.573 s	39421 KB	0

运行完成
运行时间 3.447 s
平均内存使用 39421 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!