hello-world
posts - 11, comments - 2, trackbacks - 0, articles - 0
导航
C++博客
首页
新随笔
联系
聚合
管理
<
2024年5月
>
日
一
二
三
四
五
六
28
29
30
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
1
2
3
4
5
6
7
8
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(1)
给我留言
查看公开留言
查看私人留言
随笔档案
2009年3月 (2)
2009年2月 (9)
文章分类
Waterloo
friends
topsky
members of hello_world
chinaeli
logics_space
lwc626
搜索
最新评论
1. re: Waterloo local 1999.10.02
@秋风
但直接求不好求,你是直接求的吗?可不可以说详细点
--hello_world
2. re: Waterloo local 1999.10.02
评论内容较长,点击标题查看
--秋风
阅读排行榜
1. Waterloo Local 2001.09.29 && 2002.01.26 && 2002.07.01(1776)
2. Waterloo local 2001.09.22(1582)
3. Waterloo local 2000.09.30 && 2000.09.23(1473)
4. Waterloo local contest 1998(1295)
5. Waterloo local 2001.01.27(1285)
评论排行榜
1. Waterloo local 1999.10.02(2)
2. Waterloo local 1999.09.25(0)
3. Waterloo local contest 1999(0)
4. Waterloo local 2002.09.21(0)
5. Waterloo local contest 1998(0)
Waterloo local 1999.09.25
Posted on 2009-02-09 19:02
hello_world
阅读(1144)
评论(0)
编辑
收藏
引用
Waterloo local 1999.09.25
题目分类
Fire Station
图论,最短路
Soundex
水题
Ferry Loading
DP
Dog & Gopher
水题
Gas Station Numbers
分析,倒推
补充:
Fire Station:
题目给出一些交叉路口,有
些路口建有消防站,因此每个路口都有一个离自己最近的消防站,在这些最短的距离中找出最长的!题目要求再建一个消防站(要求编号最小),使这个最长距离最短!考虑到每个路口最多只有二十条边(题目意思),所以可以用邻接表存图然!然后用Dijkstra(或者spfa)算出所有点对之间的最短距离(当然Floyd也行,但是可能要慢很多),求出刚开始的最长距离,从小到大枚举每一个路口,看是否可以减小这个最长距离即可!值得注意的是必需要建一个消防站,因此可以在已经建过的路口建!
Ferry Loading:
一看就知道是一道DP题目,开始的时候实在不知道怎么做,后来参考了一下解答:
state[i][j]表示前i个汽车能够让左边长度为j的状态,那么state[i][j] = true if and on if state[i-1][j-len[k]]=true(0<=k<i) or state[i-1][j]=true;如果前i个汽车的总长度为s,甲板的总长度为Len,那么每个状态要满足 j<=Len,s-j<=Len;
实现的时候 可以用递推的方法,那样更简单,一旦不能产生新的状态就停止!且每个状态记录是由前哪个状态变换过来的,输出的时候可以递归输出答案!
核心代码(借鉴标答):
void
print(
int
i,
int
j)
{
if
(i
==
0
)
return
;
print(i
-
1
,dp[i][j]);
printf((j
==
dp[i][j])
?
"
port\n
"
:
"
starboard\n
"
);
}
memset(dp,
-
1
,
sizeof
(dp));
dp[
0
][
0
]
=
0
;
for
(i
=
0
;i
<
n;i
++
)
{
bool
flag
=
false
;
for
(j
=
0
;j
<=
L;j
++
)
if
(dp[i][j]
>=
0
)
{
if
(j
+
len[i]
<=
L
&&
sum
-
len[i]
-
j
<=
L)
dp[i
+
1
][j
+
len[i]]
=
j,flag
=
true
;
if
(j
<=
L
&&
sum
-
j
<=
L)
dp[i
+
1
][j]
=
j,flag
=
true
;
}
if
(
!
flag)
break
;
}
Gas Station Numbers :
题目大意是给你 一个数字N,你可以交换他们每位的数字 比如 12.5 可以变成 15.2 也可以变成 2.15
你也可以把 2变成 5 ,5变成 2 ,也可以把 6变成 9 ,9 变成 6,对于由 N 所有变换而来的所有可能
,比N大的最小值是多少?
题目要找一个最小的 大于原数的值,显然倒序(从低位考虑 )考虑更方便。
当考虑到第 i (0<=i<len)位时,有几个原则:
1 能在第 i 位上变化获得答案,就绝不到第 i - 1 位上变动,尽量保持高位不变
2 若在第 i 位上有多种变化可能,选择最小的值去替换第 i 位
3 如果在第 i 位上发生变化,则有可行解,如果一直倒推到第 0 位还不能替换,则无解
4 第 i 位替换好了的话, i+1位 到 len - 1位(即之后的数)要求最小
所以在倒推的时候,可以开一个数组visit[10]记录当前可以用来替换的资源,时间复杂度只是用在排序上,为nlog(n)
只有注册用户
登录
后才能发表评论。
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © hello_world