青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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

評論

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

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

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

導航

統計

常用鏈接

留言簿(10)

隨筆分類

隨筆檔案

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美色道久久88综合亚洲精品| 欧美成人激情视频| 亚洲综合社区| 亚洲人体一区| 欧美在线视频在线播放完整版免费观看| 国产一区二区三区在线观看精品| 久久夜精品va视频免费观看| 欧美jizz19hd性欧美| 亚洲视屏一区| 欧美成人r级一区二区三区| 欧美在线免费视屏| 欧美日韩免费观看一区=区三区 | 国产色综合天天综合网| aaa亚洲精品一二三区| 亚洲国产日韩精品| 久久精品天堂| 久久综合综合久久综合| 国产目拍亚洲精品99久久精品| 亚洲福利视频一区| 红桃视频国产精品| 久久国产精品一区二区三区| 亚洲欧美国产日韩天堂区| 欧美日韩国产成人在线| 欧美国产成人精品| 亚洲精品午夜精品| 欧美激情精品久久久久久蜜臀| 亚洲人成小说网站色在线| av不卡在线观看| 国产精品裸体一区二区三区| 亚洲综合另类| 亚洲高清av在线| 一区二区三区四区五区精品视频| 欧美日韩一二三区| 亚洲一区久久| 欧美gay视频激情| 妖精视频成人观看www| 国产精品久久久一本精品| 先锋影院在线亚洲| 亚洲高清一区二| 亚洲欧美一区二区视频| 亚洲福利专区| 国产精品毛片大码女人| 久久午夜国产精品| 亚洲影院色在线观看免费| 欧美高清视频一二三区| 欧美在线日韩| 亚洲性视频网址| 亚洲国产精品一区二区第四页av| 国产精品播放| 欧美日韩在线三级| 免费久久久一本精品久久区| 亚洲香蕉成视频在线观看| 亚洲福利免费| 欧美大片免费久久精品三p | 91久久夜色精品国产九色| 国产精品资源| 国产精品美女久久久久久免费 | 国语自产偷拍精品视频偷| 国产精品劲爆视频| 国产精品激情| 国产农村妇女毛片精品久久莱园子| 久久婷婷国产综合尤物精品| 久久成人免费视频| 久久精品欧洲| 牛牛国产精品| 欧美日精品一区视频| 欧美日韩国产首页| 国产精品久久久对白| 国产精品自拍三区| 在线观看国产精品淫| 亚洲国产日韩精品| 亚洲一二三区在线观看| 久久精品一区| 91久久夜色精品国产网站| 亚洲伦理网站| 久久精品最新地址| 欧美日韩亚洲成人| 在线成人中文字幕| 亚洲欧美精品在线观看| 麻豆精品视频在线观看视频| 日韩视频在线免费观看| 性色一区二区三区| 欧美日韩精品系列| 亚洲人成人一区二区三区| 亚洲欧美日韩一区在线观看| 欧美高清在线视频| 久久久免费精品| 国产一区91| 久久国内精品视频| 一区二区三区 在线观看视| 玖玖玖国产精品| 尤妮丝一区二区裸体视频| 久久精品一本| 欧美一区二区三区电影在线观看| 欧美日韩国语| 亚洲一区二区三区四区五区黄| 亚洲精品免费一二三区| 欧美精品色网| 一区二区三区四区五区在线| 女女同性精品视频| 欧美成人在线网站| 日韩视频精品在线| 午夜精品福利一区二区蜜股av| 夜夜嗨av一区二区三区网页| 久久久久青草大香线综合精品| 亚洲欧美在线免费观看| 亚洲国产天堂网精品网站| 亚洲砖区区免费| 日韩网站在线观看| 免费在线观看一区二区| 亚洲乱码久久| 一区二区三区精品国产| 国产精品h在线观看| 久久精品成人| 六月天综合网| 亚洲欧美在线播放| 欧美在线视频在线播放完整版免费观看| 国产欧美一区二区三区国产幕精品 | 亚洲欧美日本国产有色| 国产亚洲福利| 欧美大片免费看| 国产精品免费一区二区三区在线观看| 亚欧成人精品| 欧美中文字幕视频在线观看| 一区二区三区无毛| 亚洲一区二区在线视频| 亚洲午夜精品国产| 欧美日韩亚洲一区三区| 欧美成人免费在线观看| 国产亚洲观看| 欧美自拍偷拍| 久久精品99无色码中文字幕| 国产精品久久97| 亚洲欧洲综合| 日韩午夜电影| 欧美福利电影在线观看| 欧美国产视频一区二区| 亚洲黄色有码视频| 欧美a级理论片| 99re热这里只有精品视频| 亚洲特级毛片| 国产视频久久| 欧美日韩国产三区| 亚洲男同1069视频| 欧美成年人网站| 亚洲天堂免费观看| 国模吧视频一区| 欧美激情在线播放| 91久久精品美女| 暖暖成人免费视频| 一区二区三区欧美日韩| 国产一区二区精品丝袜| 国产精品综合久久久| 欧美日韩国产成人精品| 欧美日本不卡视频| 欧美日韩中文| 欧美精品一区二区视频| 欧美一区二区三区四区在线| 日韩视频一区二区| 亚洲高清av在线| 欧美国产国产综合| 久久精品伊人| 欧美在线free| 性做久久久久久免费观看欧美| 一区二区在线观看视频| 国产美女精品视频| 国产精品久99| 国产精品一区免费视频| 国产精品久久久久久超碰| 欧美久色视频| 国产伦精品一区二区三区视频孕妇 | 欧美a级一区| 欧美日韩亚洲高清一区二区| 欧美日韩精品在线| 欧美日韩专区| 国产一区二区三区av电影| 国产一区二区中文| 一区二区三区在线视频免费观看| 国产欧美亚洲视频| 精久久久久久久久久久| 亚洲国产精品热久久| 亚洲午夜精品在线| 久久久国产精品亚洲一区| 麻豆成人av| 久久激情五月激情| 欧美激情视频一区二区三区免费| 欧美日韩国产综合网| 国产欧美日韩亚洲精品| 国产精品中文字幕在线观看| 亚洲国产精品成人精品| 亚洲视频福利| 美乳少妇欧美精品| 9久草视频在线视频精品| 久久久久久久高潮| 欧美性猛交xxxx乱大交退制版| 狠狠色丁香婷综合久久| 亚洲午夜在线视频| 最新成人av在线| 麻豆国产精品777777在线| 国产主播精品在线|