動态規劃--滑雪

題目大概：

有一個矩形滑雪場，隻能從高處滑到低的地方，可以向四個方向滑，問這個滑雪場最長的一條滑雪道是多長。

思路：

dp題。

a[i][j]為矩陣各個地方的高度。

dp[i][j]為滑到改點處的最長距離。

滑到一個點可以從它的四個方向滑過去，dp[i][j]=max（dp[i-1][j]+1,dp[i][j-1]+1，dp[i+1][j-1]+1，dp[i-1][j+1]+1）。

中間用記憶式搜尋可以減少循環次數。

感想：

無。

代碼：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
int a[101][101];
int dp[101][101];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int solve(int x, int y)
{
if (dp[x][y]>0)
    return dp[x][y];
for (int i=0;i<4;i++) {
int nx=x+dx[i];
int ny=y+dy[i];
if (0<=nx&&nx<n&&0<=ny&&ny<m&&a[nx][ny]<a[x][y]){
dp[x][y]=max(dp[x][y],solve(nx,ny)+1);
}
}
return dp[x][y];
}
int main()
{

cin>>n>>m;
memset(dp,0,sizeof(dp));
for (int i=0;i<n;i++){
            for(int j=0;j<m;j++)
            cin>>a[i][j];
}
int ans=0;
for (int i=0;i<n;i++) {
for (int j=0; j<m;j++)
        ans=max(ans,solve(i,j));
}
cout<<ans+1;

return 0;
}