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

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>
            亚洲综合三区| 亚洲国产精品成人| 曰本成人黄色| 久久精品一本| 亚洲欧美第一页| 亚洲电影在线观看| 久久综合九色欧美综合狠狠| 香蕉av777xxx色综合一区| 国产精品免费在线| 久久爱www久久做| 久久se精品一区精品二区| 国内成+人亚洲| 免费久久99精品国产自| 欧美插天视频在线播放| 99av国产精品欲麻豆| 亚洲精品男同| 91久久精品一区二区别| 欧美日韩一区二区高清| 午夜久久福利| 久久精品一区四区| 亚洲精品孕妇| 亚洲欧美日韩在线一区| 亚洲国产专区校园欧美| 一本色道久久加勒比88综合| 国产精品美女在线| 亚洲少妇自拍| 91久久国产综合久久蜜月精品| 一个人看的www久久| 亚洲综合日本| 久久精品日产第一区二区| 久久偷窥视频| 亚洲国产精品久久久久秋霞蜜臀| 久久久久久网| 亚洲伊人久久综合| 国产精品久久久久天堂| 亚洲欧美在线aaa| 久久视频在线视频| 亚洲国产合集| 欧美另类在线播放| 久久亚洲免费| 亚洲精品一级| 久久亚洲私人国产精品va| 99视频日韩| 久久九九免费视频| 亚洲第一偷拍| 国产无遮挡一区二区三区毛片日本| 老牛国产精品一区的观看方式| 欧美日韩一二三四五区| 性久久久久久久久久久久| 久久综合激情| 中文av字幕一区| 麻豆成人av| 久久精品欧美| 国产精品午夜av在线| 亚洲国产欧美日韩另类综合| 影音先锋国产精品| 欧美精品一区二| 亚洲日本黄色| 久久久久88色偷偷免费| 亚洲精品精选| 国产日韩欧美另类| 欧美激情亚洲视频| 久久国产99| 裸体丰满少妇做受久久99精品 | 一区二区激情视频| 欧美精品久久久久久久久久| 亚洲自拍16p| 欧美成人精品不卡视频在线观看 | 久久9热精品视频| 亚洲第一福利视频| 欧美日韩国产免费| 91久久精品国产| 欧美在线观看天堂一区二区三区| 亚洲性视频网站| 欧美日韩国产电影| 久久婷婷影院| 欧美一区二区日韩一区二区| 欧美在线一区二区| 亚洲视频欧洲视频| 亚洲精品1234| 黄色日韩精品| 久久综合久久久| 亚洲大片在线| 久久一本综合频道| 久久成人国产精品| 亚洲欧美日韩精品久久奇米色影视 | 亚洲国产清纯| 日韩午夜av在线| 久久本道综合色狠狠五月| 在线电影欧美日韩一区二区私密| 久久国产精品72免费观看| 久久久精品日韩欧美| 亚洲三级电影在线观看| 亚洲一区中文字幕在线观看| 欧美成人影音| 狼人天天伊人久久| 国产精品久久久久久户外露出| 亚洲国产精品久久久久| 久久国产主播精品| 欧美一区二区成人6969| 午夜精品美女自拍福到在线| 亚洲一区日韩在线| 在线亚洲免费| 亚洲一区精品电影| 亚洲午夜一二三区视频| 亚洲特级毛片| 亚洲一区免费观看| 亚洲一级片在线看| 亚洲综合欧美日韩| 欧美在线二区| 欧美一区二区三区四区高清| 久久se精品一区精品二区| 久久精品在线播放| 老司机成人网| 欧美黄色影院| 午夜精品久久久久久| 欧美一区免费视频| 欧美三级午夜理伦三级中文幕| 国产一区二区三区在线观看精品| 最新中文字幕一区二区三区| 久久国产精彩视频| 亚洲视频久久| 欧美a一区二区| 亚洲——在线| 亚洲日本黄色| 亚洲综合首页| 亚洲天堂av综合网| 1000部国产精品成人观看| 欧美国产激情二区三区| 国产视频亚洲| 欧美中文字幕| 久久国产一区二区| 国产欧美日韩精品在线| 亚洲欧美视频在线观看| 在线中文字幕一区| 亚洲在线国产日韩欧美| 在线观看视频日韩| 一区二区三欧美| 欧美在线观看网址综合| 欧美a一区二区| 一区二区三区产品免费精品久久75| 亚洲午夜精品网| 免费高清在线视频一区·| 欧美视频在线播放| 伊人伊人伊人久久| 亚洲午夜在线观看| 免费亚洲电影在线| 亚洲视频一区二区| 免费久久99精品国产自| 国产网站欧美日韩免费精品在线观看| 在线观看视频亚洲| 欧美一区二区成人6969| 亚洲精品久久在线| 久久激情视频| 国产精品久久久亚洲一区| 在线精品观看| 久久www免费人成看片高清| 亚洲精品乱码久久久久久| 久久精品女人| 国产美女精品视频免费观看| 欧美色区777第一页| 伊人成人在线| 欧美在线黄色| 日韩香蕉视频| 一本一本久久a久久精品综合麻豆 一本一本久久a久久精品牛牛影视 | 亚洲伊人伊色伊影伊综合网 | 国产欧美在线播放| 亚洲日本aⅴ片在线观看香蕉| 久久精品亚洲一区| 正在播放亚洲| 欧美日韩综合不卡| 日韩网站在线看片你懂的| 免费一级欧美片在线观看| 午夜精品久久久久久久99热浪潮| 欧美色偷偷大香| 在线亚洲欧美专区二区| 亚洲欧洲一区二区天堂久久| 久久免费观看视频| 国产在线日韩| 久久人人97超碰人人澡爱香蕉| 久久综合久久综合这里只有精品| 亚洲深夜福利| 国产精品每日更新| 性伦欧美刺激片在线观看| 美女尤物久久精品| 久久久91精品国产一区二区精品| 国产精品婷婷午夜在线观看| 亚洲资源在线观看| 亚洲午夜免费福利视频| 国产精品久久久久高潮| 亚洲欧美日韩精品综合在线观看 | 久久久久久久久一区二区| 国产一区二区三区在线观看免费视频| 午夜欧美理论片| 欧美专区一区二区三区| 伊人久久综合97精品| 欧美国产一区二区| 欧美极品一区二区三区| 亚洲视频在线视频| 亚洲一区二区三区在线播放|