POJ 1088 - 滑雪（动态规划）

本文主要是介绍POJ 1088 - 滑雪（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击打开链接（NOI省选题）

记忆化搜索

WA了一次：边界时return d[x][y] = 1; 没有跟ans比较，导致特殊情况ans等于0。

改法是将ans比较放到solve里跟最后dfs返回值比较。ans = max ( ans, dfs ( i, j ) );

状态转移：d[x][y] = max ( d[x][y], dfs ( nx, ny ) + 1 );

//	poj 1088
//  [6/11/2014 wind]
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_RC = 100;
int row, cow;
int a[MAX_RC][MAX_RC];int d[MAX_RC][MAX_RC];int dx[] = { -1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int ans = 0;int inline in ( int x, int y )
{return 0 <= x && x < row && 0 <= y && y < cow;
}int dfs ( int x, int y )
{if ( d[x][y] ){return d[x][y];}bool hasNext = false;for ( int i = 0; i < 4; i++ ){int nx = x + dx[i], ny = y + dy[i];if ( in ( nx, ny )  && a[nx][ny] < a[x][y] ){d[x][y] = max ( d[x][y], dfs ( nx, ny ) + 1 );//ans = max ( ans, d[x][y] );hasNext = true;}}if ( !hasNext )return d[x][y] = 1;return d[x][y];
}void solve()
{for ( int i = 0; i < row; i++ ){for ( int j = 0; j < cow; j++ ){ans = max ( ans, dfs ( i, j ) );}}
}int main()
{//freopen ( "in.txt", "r", stdin );scanf ( "%d%d", &row, &cow );for ( int i = 0; i < row; i++ ){for ( int j = 0; j < cow; j++ ){scanf ( "%d", &a[i][j] );}}solve();printf ( "%d\n", ans );return 0;
}

这篇关于POJ 1088 - 滑雪（动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---