滑雪
Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output
25
Source
题目类型：线性DP
算法分析：定义ans[i][j]为到该(i, j)处时最长的滑道长度，状态转移方程为：ans[i][j] = max (ans[i][j], ans[i-1][j] + 1, ans[i+1][j] + 1, ans[i][j-1] + 1, ans[i][j+1] + 1); 1 <= i <= row, 1 <= j <= col;使用记忆化搜索技术来计算，WA点：所有的高度都是严格递减的，转移过程中不要考虑两个位置的高度会相同
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <iostream> #include <fstream> #include <algorithm> #include <iomanip> #include <cstring> #include <cstdio> #include <cmath> #include <map> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <list> #include <ctime> using namespace std; const int INF = 0x7FFFFFFF; const int maxn = 100 + 66; int ans[maxn][maxn], val[maxn][maxn]; int row, col; int Solve (int x, int y) { if (ans[x][y]) return ans[x][y]; ans[x][y] = 1; if (x - 1 >= 1 && val[x][y] < val[x-1][y]) ans[x][y] = max (ans[x][y], Solve (x - 1, y) + 1); if (x + 1 <= row && val[x][y] < val[x+1][y]) ans[x][y] = max (ans[x][y], Solve (x + 1, y) + 1); if (y - 1 >= 1 && val[x][y] < val[x][y-1]) ans[x][y] = max (ans[x][y], Solve (x, y - 1) + 1); if (y + 1 <= col && val[x][y] < val[x][y+1]) ans[x][y] = max (ans[x][y], Solve (x, y + 1) + 1); return ans[x][y]; } int main() { // ifstream cin ("aaa.txt"); while (cin >> row >> col) { int i, j; for (i = 1; i <= row; i++) { for (j = 1; j <= col; j++) cin >> val[i][j]; } memset (ans, 0, sizeof (ans)); for (i = 1; i <= row; i++) { for (j = 1; j <= col; j++) Solve (i, j); } int maxval = -INF; for (i = 1; i <= row; i++) { for (j = 1; j <= col; j++) if (maxval < ans[i][j]) maxval = ans[i][j]; } cout << maxval << endl; } return 0; } |
- « 上一篇：poj1068
- poj1122：下一篇 »