hello-world
posts - 11, comments - 2, trackbacks - 0, articles - 0
导航
C++博客
首页
新随笔
联系
聚合
管理
<
2009年2月
>
日
一
二
三
四
五
六
25
26
27
28
29
30
31
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
1
2
3
4
5
6
7
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(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(1811)
2. Waterloo local 2001.09.22(1618)
3. Waterloo local 2000.09.30 && 2000.09.23(1505)
4. Waterloo local contest 1998(1312)
5. Waterloo local 2001.01.27(1298)
评论排行榜
1. Waterloo local 1999.10.02(2)
2. Waterloo local 2000.01.29(0)
3. Waterloo local 2000.09.30 && 2000.09.23(0)
4. Waterloo local 2001.01.27(0)
5. Waterloo local 2001.06.02(0)
Waterloo local 1999.09.25
Posted on 2009-02-09 19:02
hello_world
阅读(1159)
评论(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)
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
博问
Chat2DB
管理
Powered by:
C++博客
Copyright © hello_world