Posted on 2007-08-23 15:30
刘超 阅读(245)
评论(0) 编辑 收藏 引用
1
滑雪
2
Time Limit:1000MS Memory Limit:65536K
3
Total Submit:
11034
Accepted:
3437
4
5
Description
6
Michael 喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个 区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
7
8
9
10
11
Input
12
输入的第一行表示区域的行数R和列数C(
1
<=
R,C
<=
100
)。下面是R行，每行有C个整数，代表高度h，
0
<=
h
<=
10000
。
13
14
Output
15
输出最长区域的长度。
16
17
Sample Input
18
19
5
5
20
1
2
3
4
5
21
16
17
18
19
6
22
15
24
25
20
7
23
14
23
22
21
8
24
13
12
11
10
9
25
26
Sample Output
27
25
28
这道题目非常的好，解题方法也很多，可以用DP，也可以用记忆化搜索，当然还可以暴力破解，不过常规的DP就
足以解决问题了，所以我用了常规的DP来解这道题目
动规方程可以写为path[x][y] = MAX{path[x-1][y], path[x+1][y], path[x][y+1], path[x][y-1]}
如果先按排序再递推的话复杂度会相对小一些
1
#include
<
stdio.h
>
2
#include
<
string
.h
>
3
#define
MAX 100
4
5
struct
point
6
{
7
int
x,y,height;
8
}
points[MAX
*
MAX];
9
10
int
cmp(
void
const
*
a,
void
const
*
b)
11
{
12
return
(
*
(
struct
point
*
)a).height
-
(
*
(
struct
point
*
)b).height;
13
}
int
path[MAX][MAX];
14
15
int
hills[MAX][MAX];
16
const
int
direction[
4
][
2
]
=
{
{
0
,
1
}
,
{
0
,
-
1
}
,
{
1
,
0
}
,
{
-
1
,
0
}
}
;
17
18
int
main()
19
{
20
int
r, c, i, j, k, ans, x, y;
21
scanf(
"
%d%d
"
,
&
r,
&
c);
22
k
=
0
;
23
for
(i
=
0
; i
<
r;
++
i)
24
for
(j
=
0
; j
<
c;
++
j)
25
{
26
scanf(
"
%d
"
,
&
hills[i][j]);
27
points[k].x
=
i;
28
points[k].y
=
j;
29
points[k
++
].height
=
hills[i][j];
30
}
31
32
qsort(points, k,
sizeof
(
struct
point), cmp);
33
34
for
(i
=
0
; i
<
r; i
++
)
35
for
(j
=
0
; j
<
c;j
++
)
36
path[i][j]
=
0
; ans
=
0
;
37
38
for
(i
=
0
; i
<
k;
++
i)
39
{
40
for
(j
=
0
;j
<
4
;
++
j)
41
{
42
x
=
points[i].x
+
direction[j][
0
];
43
y
=
points[i].y
+
direction[j][
1
];
44
if
(x
>=
0
&&
x
<
r
&&
y
>=
0
&&
y
<
c
&&
hills[x][y]
<
points[i].height
&&
path[points[i].x][points[i].y]
<=
path[x][y])
45
path[points[i].x][points[i].y]
=
path[x][y]
+
1
;
46
}
47
if
(ans
<=
path[points[i].x][points[i].y])
48
ans
=
path[points[i].x][points[i].y];
49
}
50
printf(
"
%d\n
"
,ans
+
1
);
51
return
0
;
52
}