題解 P1434 【滑雪】

題目連結

此題運用功能強大的 ~~暴力搜尋~~

 記憶化搜尋才是重點！！！

然而，這是一道經典的DP問題

 如果我們用$dis[i][j]$來表示坐标為$(i,j)$時的高度

 $cnt[i][j]$ 是我們的記憶化數組

在合法的前提下，就有狀态轉移方程：

 $dis[i][j]=max(dis[i-1][j],dis[i][j-1],dis[i+1][j],dis[i][j+1])$

好啦，直接上代碼吧：其實挺暴力:

 $2^{33……}$

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;//頭檔案不說啥
int dis[100][100];
int cnt[100][100];
int row,col;//行列數
inline int DP(int i, int j)//狀态轉移
{
     int max1=0;
    
    if(cnt[i][j]>0)
        return cnt[i][j];//記憶化，如果被搜過，跳就好
    
    //判斷dis[i][j-1]是否合法
    if(j-1>=0)//邊界條件
      if(dis[i][j]>dis[i][j-1])//轉移條件
        if(max1<DP(i,j-1))
          max1=DP(i,j-1);
    
    //判斷dis[i][j+1]是否合法
    if(j+1<=col-1)
      if(dis[i][j]>dis[i][j+1])
        if(max1<DP(i,j+1))
            max1=DP(i,j+1);
    
    //判斷dis[i-1][j]是否合法
     if(i-1>=0)
        if(dis[i][j]>dis[i-1][j])
        if(max1<DP(i-1,j))
          max1=DP(i-1,j);
    
    //判斷dis[i+1][j]是否合法
    if(i+1<=row-1)
      if(dis[i][j]>dis[i+1][j])
        if(max1<DP(i+1,j))
          max1=DP(i+1,j);
 
    return cnt[i][j]=max1+1;//轉移
}
int main()
{
    scanf("%d%d",&row,&col);//輸入
     for(int i=0;i<=row-1;i++)
        for(int j=0;j<=col-1;j++)
          scanf("%d",&dis[i][j]);

    for(int i=0;i<=row-1;i++)//狀态轉移
        for(int j=0;j<=col-1;j++)
        DP(i, j);
        
    for(int i=0;i<=row-1;i++)//找最大值
        for(int j=0;j<=col-1;j++)
         if(cnt[0][0]<cnt[i][j])
            cnt[0][0]=cnt[i][j];

    printf("%d",cnt[0][0]);//輸出
    return 0;//程式拜拜
}