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

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個人一起過橋,所花時間由那個需要最長時間的人決定。問怎么過橋所需要的時間最短。
    由于題目的數(shù)據(jù)量不是很大,我直接用dfs搜了下所有的情況然后取最小的時間。貌似還有數(shù)學(xué)方法能很輕松的解決,不過還沒想到。
#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

在劉汝佳的《算法藝術(shù)與信息學(xué)競賽》上貪心算法練習(xí)題有這么一個題,應(yīng)該是貪心可以吧  回復(fù)  更多評論   


只有注冊用戶登錄后才能發(fā)表評論。
相關(guān)文章:
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

導(dǎo)航

統(tǒng)計

常用鏈接

留言簿(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>
            91久久在线| 欧美国产日韩a欧美在线观看| 免费看av成人| 老鸭窝毛片一区二区三区| 亚洲欧洲日产国码二区| 亚洲国产日韩欧美在线动漫| 欧美精品v国产精品v日韩精品| 日韩视频免费观看高清完整版| 亚洲片区在线| 国产精品国产三级国产普通话99| 午夜亚洲性色视频| 久久久av水蜜桃| 亚洲欧洲一区二区天堂久久| 亚洲乱码视频| 国内久久婷婷综合| 亚洲高清123| 国产精品日本欧美一区二区三区| 久久激情综合| 欧美激情影院| 久久国产欧美日韩精品| 免费日韩视频| 午夜精品久久| 欧美国产91| 久久九九久久九九| 欧美日韩国产专区| 久久日韩粉嫩一区二区三区| 欧美成年人视频网站| 亚洲欧美日韩综合| 麻豆精品视频在线观看| 亚洲主播在线观看| 欧美 日韩 国产在线| 亚洲欧美日韩国产综合| 美女精品网站| 欧美一级日韩一级| 欧美极品影院| 久久综合久久美利坚合众国| 欧美日韩一区二区三区在线视频 | 欧美巨乳波霸| 久久久亚洲午夜电影| 欧美日韩精品一区二区| 美国成人直播| 国产欧美一区二区视频| 亚洲三级免费观看| 亚洲国产影院| 久久精品国产亚洲aⅴ| 午夜免费电影一区在线观看| 欧美激情区在线播放| 老司机成人在线视频| 国产精品亚洲综合色区韩国| 亚洲巨乳在线| 亚洲免费观看高清完整版在线观看熊 | 久久深夜福利| 久久久久久久久蜜桃| 国产精品一区二区在线观看不卡 | 久久在线免费| 国产一区二区三区在线播放免费观看 | 亚洲国产精品第一区二区| 在线高清一区| 久久久久久9999| 久久一区激情| 在线观看精品视频| 麻豆精品在线视频| 欧美成人蜜桃| 亚洲欧洲美洲综合色网| 美玉足脚交一区二区三区图片| 久久久欧美精品| 韩国一区二区在线观看| 欧美在线三区| 麻豆av一区二区三区久久| 狠狠色综合色综合网络| 久久亚洲欧美| 亚洲国产成人av好男人在线观看| 亚洲国产激情| 欧美韩国日本一区| 一区二区欧美精品| 欧美亚洲在线播放| 国产一区二区按摩在线观看| 久久激情婷婷| 亚洲国产精品久久久久婷婷884| 91久久精品日日躁夜夜躁国产| 蜜臀91精品一区二区三区| 亚洲国产另类精品专区| 一区二区三区国产盗摄| 国产精品拍天天在线| 久久狠狠亚洲综合| 亚洲国产日韩一级| 亚洲永久字幕| 韩国av一区二区三区四区| 卡一卡二国产精品| 99re视频这里只有精品| 久久成人综合网| 亚洲国产视频一区| 国产精品久久久久久久久果冻传媒 | 亚洲午夜视频在线| 国产综合色在线| 欧美精选在线| 欧美一区二区三区播放老司机| 欧美高清视频一区| 亚洲欧美日韩区| 91久久综合| 国产精品视频一二三| 猛干欧美女孩| 性久久久久久久久久久久| 亚洲福利视频网站| 久久精品二区三区| 一二美女精品欧洲| 精品二区视频| 国产精品亚洲激情 | 亚洲黄网站在线观看| 小黄鸭精品密入口导航| 亚洲人成网站在线观看播放| 国产精品亚洲人在线观看| 欧美成人激情视频| 久久精品中文字幕一区| 99精品欧美一区| 欧美成人久久| 久久亚洲视频| 久久爱www.| 99re亚洲国产精品| 亚洲国产日韩欧美在线动漫| 国产精自产拍久久久久久| 欧美日韩国产免费观看| 久久亚洲精品网站| 久久国产一区二区| 亚洲欧美一级二级三级| 夜夜精品视频| 亚洲人成艺术| 亚洲国产日韩欧美一区二区三区| 久久久亚洲综合| 久久不射中文字幕| 欧美一区二区在线免费观看| 99视频精品免费观看| 亚洲日本va在线观看| 亚洲成色777777女色窝| 韩国三级在线一区| 国内精品国产成人| 狠狠色狠狠色综合| 国语精品中文字幕| 狠色狠色综合久久| 精品999在线观看| 今天的高清视频免费播放成人| 国产精品久久久久一区二区三区| 欧美日韩在线视频首页| 欧美日韩免费在线观看| 欧美日韩午夜激情| 欧美日韩综合| 国产精品私房写真福利视频| 国产精品久久久久久久久久免费 | 欧美日韩一视频区二区| 欧美精品久久一区| 欧美视频一区在线观看| 国产精品成人va在线观看| 国产精品乱码一区二区三区| 国产精品久久久久久久午夜 | 伊人婷婷久久| 亚洲精品视频在线看| 一区二区三区四区国产精品| 国产精品99久久久久久www| 亚洲一区二区三区在线观看视频 | 欧美99在线视频观看| 欧美刺激性大交免费视频| 亚洲国内精品| 亚洲少妇最新在线视频| 亚洲韩国一区二区三区| 亚洲日本黄色| 国产精品免费一区豆花| 亚洲黄色av| 伊人激情综合| 午夜视频久久久| 欧美1级日本1级| 亚洲女优在线| 欧美日韩精品一区二区天天拍小说| 久久视频在线视频| 亚洲无限乱码一二三四麻| 亚洲欧美欧美一区二区三区| 欧美一区二区三区四区在线 | 久久亚洲不卡| 欧美好骚综合网| 国产乱码精品一区二区三| 狠狠操狠狠色综合网| 99精品免费网| 久久一区二区精品| 亚洲精选视频在线| 久久xxxx| 欧美日韩在线观看一区二区| 国产精品视频免费观看www| 在线电影国产精品| 性欧美1819性猛交| 亚洲日本一区二区| 欧美一区二区三区成人| 欧美日韩理论| 在线免费观看欧美| 欧美在线free| 亚洲美女在线国产| 久久久久久夜| 国产午夜精品久久久久久久| 亚洲视频1区2区| 亚洲福利视频三区| 久久亚洲高清| 韩日精品在线|