关于公司网站建设情况的汇报,网站建设公司网,php管理系统,江苏建设通网站http://poj.org/problem?id1088 这是一道dp入门题#xff0c;不过我一直没想明白应该怎么dp。今天#xff0c;在做自己学校oj的算法基础题时看到这题#xff0c;标注着dp的分类#xff0c;加上我一直都比较喜欢做dp题#xff0c;于是我就决心今晚要把这道入门题切了。 题…http://poj.org/problem?id1088 这是一道dp入门题不过我一直没想明白应该怎么dp。今天在做自己学校oj的算法基础题时看到这题标注着dp的分类加上我一直都比较喜欢做dp题于是我就决心今晚要把这道入门题切了。 题目是中文的题目大意就免了吧…… 晚上做dp题的时候我先是看见类似这题的一维单调增子序列那题轻松AC了。但是面对这个我隔了很长时间没想的二维dp题我想了很久都想不到怎么dp。因为这题在我们学校的oj里是全部计算机专业都要知道怎么做的所以题目下面有详细的解释而且觉得那个题解是相当的浅显易懂。 下面是那个解释 动规算法思路:
f矩阵与原高度矩阵一样大小f(i,j)表示从(i,j)位置开始滑可以获得的最大滑道的长度。算法步骤
1将高度矩阵从低到高排序
2按滑点从低到高依次计算最长滑道的长度存于f(i,j)。
3f(i,j)中的最大值即原题所求。 我依据它的描述以及我对这题的了解解释一遍 我们需要的是一个用来储存原本高度的二维数组一个用来记忆dp状态的数组以及一个储存高度以及该高度所在的坐标的结构体数组。先说明一下我是为了方便自己所以除了结构体数组外其他两个数组都是开大了的。因为poj的题目中数据是0h10000所以我用-1作为图的边界条件dp数组正常清零。为了方便遍历四个邻接的坐标所以我定义了四个方向向量。 读入数据的时候数据要被处理放到相应的结构类型中。 然后在核心处理前我们的dp需要一个高度单调增大的但是对应的坐标不会改变。结构体整块的数据移动就可以保留上述预处理的高度块的坐标。这里可以直接用qsort进行对高度的快排。这个预处理是后面dp的关键。 在预处理后由低到高处理每个高度块所指示的坐标。对于每一个坐标搜索该坐标周围的dp最大值dp值的含义是从该点出发最长可以滑多远那么被处理的高度块其dp值就是上述最大值加一。然后为什么可以这样做就是理解整道题的关键。 可能会有人有这样的疑问在处理的时候刚开始周围的点不是还没知道dp值吗为什么也可以直接利用 解答这个问题的关键就在于我们刚开始的时候dp矩阵已经清零。假设从第一个坐标开始显然这个坐标是最矮的高度块所对应的坐标所以在这周围四块不存在比它矮的那么一块所以它的dp值是1。同时我们观察到这时周围四块的dp值都是0所以这块必定会变为1。其他的也同理如果周围存在比当前块高的块那么这个块肯定是还没被赋值的也就是默认的0。就是说当前块无法继承这个比自己要高的块的dp值。此时为0是合理的 找到所有dp值中的最大值后输出。 这题我wa了几次主要是刚开始没想到周围的高度块是允许比当前的大的所以一个大小符号导致我浪费了不少时间。 下面是我的代码 View Code 1 #include stdio.h2 #include string.h3 #include math.h4 #include stdlib.h5 6 #define Reset(a) memset(a, 0, sizeof(a))7 #define MAX 10000000008 9 int dir[4][2]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
10
11 struct high
12 {
13 int x, y;
14 int h;
15 };
16
17 int cmp(const void *_a, const void *_b)
18 {
19 struct high a*(struct high *)_a;
20 struct high b*(struct high *)_b;
21
22 return a.h-b.h;
23 }
24
25 int main()
26 {
27 int n, m;
28 while (~scanf(%d%d, n, m))
29 {
30 int h[n2][m2], dp[n2][m2];
31 struct high rec[n*m];
32
33 memset(h, 255, sizeof(h));
34 for (int i1; in; i)
35 for (int j1; jm; j)
36 {
37 scanf(%d, h[i][j]);
38 rec[(i-1)*mj-1].hh[i][j];
39 rec[(i-1)*mj-1].xi;
40 rec[(i-1)*mj-1].yj;
41 }
42 Reset(dp);
43 qsort(rec, n*m, sizeof(struct high), cmp);
44 int ans0;
45 for (int i0, tmpn*m; itmp; i)
46 {
47 int max0;
48
49 for (int j0; j4; j)
50 {
51 if (max dp[rec[i].x-dir[j][0]][rec[i].y-dir[j][1]]1
52 h[rec[i].x-dir[j][0]][rec[i].y-dir[j][1]]!h[rec[i].x][rec[i].y])
53 max dp[rec[i].x-dir[j][0]][rec[i].y-dir[j][1]]1;
54 dp[rec[i].x][rec[i].y] max;
55 }
56 if(ansmax)
57 ansmax;
58 }
59 /**
60 for (int i1; in; i)
61 {
62 for (int j1; jm; j)
63 printf(%4d , dp[i][j]);
64 puts();
65 }
66 /**/
67 printf(%d\n, ans);
68 }
69
70 return 0;
71 } 转载于:https://www.cnblogs.com/LyonLys/archive/2012/04/27/poj_1088_Lyon.html
