SRM 146 DIV 2 1000

Problem Statement

    

A well-known riddle goes like this: Four people are crossing an old bridge. The bridge cannot hold more than two people at once. It is dark, so they can't walk without a flashlight, and they only have one flashlight! Furthermore, the time needed to cross the bridge varies among the people in the group. For instance, let's say that the people take 1, 2, 5 and 10 minutes to cross the bridge. When people walk together, they always walk at the speed of the slowest person. It is impossible to toss the flashlight across the bridge, so one person always has to go back with the flashlight to the others. What is the minimum amount of time needed to get all the people across the bridge?

In this instance, the answer is 17. Person number 1 and 2 cross the bridge together, spending 2 minutes. Then person 1 goes back with the flashlight, spending an additional one minute. Then person 3 and 4 cross the bridge together, spending 10 minutes. Person 2 goes back with the flashlight (2 min), and person 1 and 2 cross the bridge together (2 min). This yields a total of 2+1+10+2+2 = 17 minutes spent.

You want to create a computer program to help you solve new instances of this problem. Given an vector <int> times , where the elements represent the time each person spends on a crossing, your program should return the minimum possible amount of time spent crossing the bridge.

Definition

    
Class: BridgeCrossing
Method: minTime
Parameters: vector <int>
Returns: int
Method signature: int minTime(vector <int> times)
(be sure your method is public)
    很有意思的一个题目,大概是说有n个人(1<=n<=6)要过一个独木桥,独木桥每次最多只能过2个人。过桥必须要灯笼,而且只有一盏灯笼。如果2个人一起过桥,所花时间由那个需要最长时间的人决定。问怎么过桥所需要的时间最短。
    由于题目的数据量不是很大,我直接用dfs搜了下所有的情况然后取最小的时间。貌似还有数学方法能很轻松的解决,不过还没想到。
#include <iostream>
#include 
<vector>
using namespace std;

class BridgeCrossing{
public:
    
int len,time,cross[6],best;
    
void dfs(int n,bool flash,vector<int> times);
    
int minTime(vector<int> times);
}
;
void BridgeCrossing::dfs(int n, bool flash, vector<int> times){
    
if(n==0){
        best
=(best>time)?time:best;
        
return;
    }

    
if(flash){
        
for(int i=0;i<len;i++)
            
for(int j=i+1;j<len;j++)
                
if(cross[i] && cross[j]){
                    cross[i]
=cross[j]=false;
                    time
+=max(times[i],times[j]);
                    dfs(n
-2,!flash,times);
                    time
-=max(times[i],times[j]);
                    cross[i]
=cross[j]=true;
                }

    }

    
else{
        
for(int i=0;i<len;i++)
            
if(!cross[i]){
                cross[i]
=true;
                time
+=times[i];
                dfs(n
+1,!flash,times);
                time
-=times[i];
                cross[i]
=false;
            }

    }

}

int BridgeCrossing::minTime(vector<int> times){
    best
=INT_MAX;
    len
=times.size();
    time
=0;
    
for(int i=0;i<6;i++) cross[i]=true;
    
if(len==1) best=times[0];
    
else dfs(len,true,times);
    
return best;
}

posted on 2009-05-27 00:59 极限定律 阅读(562) 评论(1)  编辑 收藏 引用 所属分类: TopCoder

评论

# re: SRM 146 DIV 2 1000 2010-03-05 11:05 3214668848

在刘汝佳的《算法艺术与信息学竞赛》上贪心算法练习题有这么一个题,应该是贪心可以吧  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年5月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(10)

随笔分类

随笔档案

友情链接

搜索

最新评论

阅读排行榜

评论排行榜