[UVa] 10285 - Longest Run on a Snowboard

題目網址: https://goo.gl/KnbRez

題意:
(from luckycat)


解法:
很簡單的 DP 喔！定義遞迴式 dp[x][y] 代表 從位子 ( x, y ) 開始能夠走的最長路長度。
當與 ( x, y ) 相鄰的點 ( nx, ny ) 比 ( x, y ) 低時， dp[x][y] = max{ dp[x][y], dp[nx][ny]+1 }。
接著把所有的點從最低的開始訪問起，就可以算出所有的值囉。
最後只要找出最大的 dp[x][y] 就是答案。

TAG: DP

注意:

程式碼:

	/**
	* Tittle: 10285 - Longest Run on a Snowboard
	* Author: Cheng-Shih, Wong
	* Date: 2015/06/05
	*/
	// include files
	#include <bits/stdc++.h>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 105
	struct Node {
	int x, y;
	int h;
	Node( int _x=0, int _y=0, int _h=0 ):
	x(_x), y(_y), h(_h) {}
	const bool operator<( const Node &op ) const {
	return h < op.h;
	}
	};
	typedef vector<Node> VN;
	// declarations
	int t;
	int r, c;
	char name[100];
	int ht[N][N];
	VN board;
	int dp[N][N];
	const int dx[4] = { -1, 0, 1, 0 };
	const int dy[4] = { 0, 1, 0,-1 };
	// functions
	void input( void )
	{
	scanf( "%s%d%d", name, &r, &c );
	board.clear();
	FOR( i, 1, r ) FOR( j, 1, c ) {
	scanf( "%d", &ht[i][j] );
	board.push_back( Node(i,j,ht[i][j]) );
	}
	}
	void solve( void )
	{
	sort( board.begin(), board.end() );
	clr( dp, 0 );
	static int nx, ny;
	FOR( i, 1, r ) FOR( j, 1, c )
	dp[i][j] = 1;
	for( Node nd : board ) {
	FOR( dir, 0, 3 ) {
	nx = nd.x+dx[dir];
	ny = nd.y+dy[dir];
	if( ht[nx][ny]>=ht[nd.x][nd.y] ) continue;
	dp[nd.x][nd.y] = max( dp[nd.x][nd.y], dp[nx][ny]+1 );
	}
	}
	int ans = 0;
	FOR( i, 1, r ) FOR( j, 1, c )
	ans = max( ans, dp[i][j] );
	// output
	printf( "%s: %d\n", name, ans );
	}
	// main function
	int main( void )
	{
	// input
	scanf( "%d", &t );
	while( t-- ) {
	input();
	solve();
	}
	return 0;
	}

view raw 10285 - Longest Run on a Snowboard.cpp hosted with ❤ by GitHub