Saturday, October 30, 2010

poj_3404_Bridge_over_a_rough_river.cpp

Problem Links:


poj3404,

Problem:


Bridge over a rough river















Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 3063Accepted: 1211


Description



A group of N travelers (1 ≤ N ≤ 50) has approached an old and shabby bridge and wishes to cross the river as soon as possible. However, there can be no more than two persons on the bridge at a time. Besides it's necessary to light the way with a torch for safe crossing but the group has only one torch.

Each traveler needs ti seconds to cross the river on the bridge; i=1, ... , N (ti are integers from 1 to 100). If two travelers are crossing together their crossing time is the time of the slowest traveler.

The task is to determine minimal crossing time for the whole group.



Input


The input consists of two lines: the first line contains the value of N and the second one contains the values of ti (separated by one or several spaces).


Output


The output contains one line with the result.


Sample Input
4
6 7 6 5

Sample Output
29

Source
Northeastern Europe 2001, Western Subregion

Solution:


Just like POJ 1700;

Source Code:


[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Fri May 21 15:37:01 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

long long crossriver(vector<int> v, int T)
{
if (T == 1)
{
return v[0];
}
if (T == 2)
{
return v[1];
}
if (T == 3)
{
return v[0] + v[1] + v[2];
}
if (v[0] + 3 * v[1] + v[T - 1] > 2 * v[0] + v[1] + v[T - 2] + v[T - 1])
{
return 2 * v[0] + v[T - 2] + v[T - 1] + crossriver(v, T - 2);
}
else
{
return v[0] + 2 * v[1] + v[T - 1] + crossriver(v, T - 2);
}
}

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int T;
while(cin >> T)
{
vector<int> v;
for(int i=0; i<T; i++)
{
int number;
cin >> number;
v.push_back(number);
}
sort(v.begin(), v.end());
cout << crossriver(v, T) << endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

No comments :