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

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>
            欧美肥婆在线| 最新国产精品拍自在线播放| 亚洲国产一区二区三区高清| 欧美激情麻豆| 99在线精品观看| 99精品国产在热久久| 国产精品成人一区| 午夜精品久久久久久久99樱桃| 亚洲性色视频| 国产综合av| 亚洲国产老妈| 国产精品亚洲综合| 久久午夜国产精品| 欧美国产综合视频| 欧美一区二区福利在线| 久久久视频精品| 日韩小视频在线观看专区| 一区二区三区欧美激情| 国产伊人精品| 亚洲老司机av| 国产一区视频在线观看免费| 亚洲精品1区2区| 国产欧美亚洲一区| 亚洲激情在线视频| 韩日精品视频| 一区二区欧美亚洲| 激情91久久| 亚洲视频中文字幕| 亚洲国产精品传媒在线观看| 这里只有精品视频在线| 亚洲第一在线视频| 亚洲一区二区三区精品在线| 亚洲精品国偷自产在线99热| 亚洲综合欧美日韩| 亚洲日本久久| 欧美在线高清视频| 亚洲无毛电影| 欧美顶级艳妇交换群宴| 午夜性色一区二区三区免费视频| 久久亚洲风情| 久久精品国产亚洲aⅴ| 欧美另类69精品久久久久9999| 久久久噜噜噜久久| 国产精品毛片va一区二区三区 | 欧美性视频网站| 牛夜精品久久久久久久99黑人 | 久久婷婷国产综合国色天香| 欧美一区二视频| 欧美色图天堂网| 亚洲高清不卡| 亚洲第一综合天堂另类专| 亚洲欧美韩国| 午夜精品久久久久久久| 欧美视频导航| 亚洲免费电影在线观看| 亚洲精品国产品国语在线app| 久久中文精品| 欧美电影免费观看高清| 国产乱码精品一区二区三| 一本色道88久久加勒比精品| 日韩一级黄色片| 欧美日韩国产小视频在线观看| 亚洲激情在线视频| 一本色道久久综合精品竹菊| 欧美精品一二三| 亚洲精品影视在线观看| 亚洲人成在线播放网站岛国| 欧美xx69| 亚洲免费av观看| 亚洲桃色在线一区| 国产精品一区二区女厕厕| 亚洲小说欧美另类婷婷| 欧美一乱一性一交一视频| 国产精品一区二区久久| 先锋a资源在线看亚洲| 久久久精品日韩欧美| 国内久久精品| 欧美91精品| 一本久久综合| 久久久久.com| 在线日本成人| 欧美破处大片在线视频| 99一区二区| 欧美在线影院| 亚洲国产精品传媒在线观看| 欧美精品一区二区三区视频| 亚洲欧美乱综合| 国产精品www| 欧美一区二区| 欧美成人免费全部| 久色成人在线| 亚洲小视频在线观看| 亚洲欧美久久久久一区二区三区| 国产精品久久久久久久电影 | 美女主播精品视频一二三四| 亚洲电影下载| 欧美视频一区在线| 久久精品女人的天堂av| 亚洲国产精品毛片| 性色一区二区| 亚洲欧洲综合另类| 国产精品美女久久久久久久| 久久久一本精品99久久精品66| 最新精品在线| 老色批av在线精品| 9人人澡人人爽人人精品| 日韩视频免费| 久久久精品动漫| 日韩一区二区电影网| 国产精品一区视频| 欧美电影免费观看高清| 欧美一区二区三区男人的天堂| 亚洲丰满在线| 久久精品av麻豆的观看方式 | 欧美激情第10页| 香蕉乱码成人久久天堂爱免费| 亚洲精品激情| 美日韩精品视频| 校园激情久久| 在线一区亚洲| 亚洲日本成人| 18成人免费观看视频| 国产精品高潮粉嫩av| 欧美精品在线网站| 快射av在线播放一区| 香蕉免费一区二区三区在线观看| 一区二区三区色| 亚洲激情亚洲| 亚洲国产婷婷香蕉久久久久久| 免费观看国产成人| 久久色中文字幕| 欧美影院午夜播放| 亚洲欧美第一页| 亚洲性视频网站| 一区二区三区免费观看| 亚洲美女视频| 91久久综合| 91久久精品www人人做人人爽| 精品动漫3d一区二区三区免费| 国产日韩欧美a| 国产模特精品视频久久久久| 国产精品视区| 国产区在线观看成人精品| 欧美午夜久久| 国产欧美午夜| 韩国女主播一区二区三区| 国产一区欧美| 在线观看视频亚洲| 亚洲观看高清完整版在线观看| 99re6这里只有精品| 亚洲黄色免费电影| 亚洲国产欧美日韩精品| 欧美国产视频一区二区| 欧美成人免费观看| 亚洲国产视频一区| 亚洲免费观看高清完整版在线观看熊| 亚洲国产欧美不卡在线观看| 亚洲精品久久久蜜桃| 一本久道久久综合中文字幕| 亚洲一区精彩视频| 欧美在线观看一二区| 久久一二三国产| 欧美大色视频| 国产精品对白刺激久久久| 国产精品日韩久久久| 国产综合精品一区| 亚洲人成在线观看网站高清| 亚洲深夜福利在线| 久久高清免费观看| 亚洲国产黄色| 午夜精彩国产免费不卡不顿大片| 亚洲欧美综合精品久久成人| 久久久久久久综合狠狠综合| 欧美精品一区二区在线观看| 国产精品视频不卡| 一区视频在线| 亚洲淫性视频| 欧美暴力喷水在线| 日韩午夜电影| 快射av在线播放一区| 欧美日韩免费在线视频| 极品尤物av久久免费看| 中文av一区特黄| 久久精品一本| 亚洲美女视频在线观看| 欧美中文字幕在线播放| 欧美日韩精品一区二区| 国产综合色产在线精品| 亚洲视频图片小说| 久久久av毛片精品| 最新国产成人av网站网址麻豆| 欧美综合第一页| 欧美日本国产一区| 激情成人综合| 午夜精品一区二区三区在线 | 久久精品99无色码中文字幕| 日韩亚洲欧美一区| 免费不卡在线观看| 国产欧美一区二区色老头| 一区二区久久久久|