posts - 11, comments - 2, trackbacks - 0, articles - 0

Waterloo local 1999.09.25

Posted on 2009-02-09 19:02 hello_world 阅读(1157) 评论(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   知识库   博问   管理