洛谷P 1434[SHOI 2002]スキー問題解
9712 ワード
記憶化検索、詳細はコードと1冊の通を参照してください
#include
using namespace std;
int dx[4]={0, 0, 1, -1};
int dy[4]={1, -1, 0, 0};
int r, c, a[110][110], dp[110][110], ans;
int dfs(int x, int y) {
if(dp[x][y]) {
return dp[x][y];
}
dp[x][y] = 1;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 1 && nx <= r && ny >= 1 && ny <= c && a[nx][ny] < a[x][y]) {
dfs(nx , ny);
dp[x][y] = max(dp[x][y] , dp[nx][ny] + 1);
}
}
return dp[x][y];
}
int main () {
cin >> r >> c;
for(int i = 1; i <= r; i++)
for(int j = 1; j <= c; j++)
cin >> a[i][j];
for(int i = 1; i <= r; i++)
for(int j = 1; j <= c; j++)
ans = max(ans , dfs(i , j));
cout << ans << endl;
return 0;
}