Winder 最近在玩一個數(shù)字游戲，該游戲是在一個n*m 的網(wǎng)格上進(jìn)行的，每個格子上有一個數(shù)字，代表這個格子的數(shù)值。玩家需要從網(wǎng)格的左上角的格子走到右下角的格子，每次只能向右或者向下走，并且不能回頭。玩家每經(jīng)過一個格子可以選擇分值是否加上該格子的數(shù)值，每次游戲的初始分?jǐn)?shù)都是0。

Winder 想知道在每場游戲，他最多能夠得到多少分值。但是，Winder 很懶，所以你必須幫他來完成這件事。

數(shù)據(jù)輸入

輸入第一行兩個正整數(shù)N 和M（0<N、M<=15）。接下來有N 行，每行M 個整數(shù)。

數(shù)據(jù)輸出

輸出一行一個整數(shù)，表示該場游戲能取得的最高分?jǐn)?shù)sum。（保證sum 在32 位整數(shù)范圍內(nèi)）。

上面這個問題就是numberGame，考慮到每一步都有且只有向右和向左兩個選擇，故用遞歸算法會很方便，代碼如下：

復(fù)制代碼代碼如下:

#include<stdio.h>
#include<iostream>
#include<windows.h>
#pragma comment(lib,"winmm.lib")
using namespace std;
int j=0;
int go(int kc,int *Ac,int wc,int nc)
{
    if(kc>=j) return wc;
    if(kc<j)
    {
        if((kc+1)%5==0)
            return go(kc+nc,Ac,Ac[kc]+wc,nc);
        else
            return go(kc+1,Ac,Ac[kc]+wc,nc)>go(kc+nc,Ac,Ac[kc]+wc,nc)?go(kc+1,Ac,Ac[kc]+wc,nc):go(kc+nc,Ac,Ac[kc]+wc,nc);
    }
}
void main()
{
    int m,n;
    DWORD   t1,   t2;
    cin>>m>>n;
    int *A,i,w=0;
    A=new int [m*n];
    for(i=0;i<m*n;i++)
    {
        if(i!=0&&i%n==0)cout<<endl;
        cin>>A[i];
    }
    j=m*n;
    t1=timeGetTime();
    int max=go(0,A,w,n);
    cout<<max;
    t2=timeGetTime();
    cout<<"the time it takes:"<<t2-t1;
}

代碼執(zhí)行時間為46MS，由于最大權(quán)值路徑上每個節(jié)點的前驅(qū)只能是其上方的節(jié)點或其左邊的節(jié)點（最左的節(jié)點除外），故可用一個一維數(shù)組存儲每個節(jié)點前驅(qū)的最大權(quán)值，代碼如下：

復(fù)制代碼代碼如下:

#include<stdio.h>  
int i,j,dp[16],n,m,v;     
void main(){     
    scanf("%d%d",&n,&m);  
    for(i=0;i<n;i++)     
         for(j=1;j<=m;j++){     
             scanf("%d",&v);     
             if(dp[j]<dp[j-1])dp[j] = dp[j-1];     
             dp[j]+= v>0?v:0;                                      
         }     
    printf("%d\n",dp[m]);   
}

此代碼用了類似迭代的算法，代碼執(zhí)行時間為30MS，可知此代碼效率比上面的代碼效率高，并且代碼要比前者簡單的多。

您可能感興趣的文章: