• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 極限定律 閱讀(659) 評論(1)  編輯 收藏 引用 所屬分類: TopCoder

            評論

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

            在劉汝佳的《算法藝術與信息學競賽》上貪心算法練習題有這么一個題,應該是貪心可以吧  回復  更多評論   

            <2009年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久久高潮毛片免费全部播放| 久久久久无码精品| 97久久精品人人做人人爽| 精品国产一区二区三区久久| 人妻无码αv中文字幕久久 | 欧美久久综合性欧美| 亚洲?V乱码久久精品蜜桃| 无码精品久久久久久人妻中字 | 丰满少妇人妻久久久久久| 亚洲欧美另类日本久久国产真实乱对白| 久久国产成人午夜AV影院| 亚洲国产精品无码久久一线| 99麻豆久久久国产精品免费| 久久久久亚洲av综合波多野结衣| 亚洲AV无码久久寂寞少妇| 婷婷综合久久中文字幕| 狠狠色丁香久久婷婷综合蜜芽五月| 久久精品嫩草影院| 久久SE精品一区二区| 成人精品一区二区久久久| 77777亚洲午夜久久多喷| 亚洲?V乱码久久精品蜜桃 | 久久只有这里有精品4| 久久精品www人人爽人人| 久久伊人五月天论坛| 九九久久精品无码专区| 久久久久国产精品熟女影院| 久久国产精品免费一区二区三区| 青青草原精品99久久精品66| 久久久久无码中| 久久免费99精品国产自在现线 | 亚洲精品无码专区久久同性男| 久久99国产精品一区二区| 蜜臀av性久久久久蜜臀aⅴ | 欧美久久天天综合香蕉伊| 久久亚洲高清观看| 国产韩国精品一区二区三区久久| 精品无码久久久久久尤物| 久久成人国产精品| 浪潮AV色综合久久天堂| 色狠狠久久AV五月综合|