# 桥梁和火炬问题程序

## 问题陈述

“桥梁和火炬”问题表明，您需要一定的时间才能跨过桥梁。 由于时间到了，它包含正整数。 随着时间的流逝，我们得到了一座桥梁，一个人需要跨越。 这座桥一次只能允许两个人越过。 他们穿越时手持火炬。 而且因为只有一个火炬。 来自另一边的一个人应返回并把火炬带回到起点。 当两个人越过桥时，他们可以以较慢的人的速度越过。 找到所有人都可以过桥的最短总时间。

## 使用案列

`timeToCross = {1, 2, 3}`
`6`

## 代码

### 桥梁和火炬问题的C ++代码

```#include <bits/stdc++.h>
using namespace std;

int solveBridgeAndTorchProblem(int mask, bool direction, vector<int> &timeToCross, vector<vector<int>> &dp)
{
int n = timeToCross.size();
// if nobody is left to transfer
return 0;

int res = 0;
// transfer people from left to right (from destination to start)
if (direction == 1) {
int minRow = INT_MAX, person;
for (int i = 0; i < n; ++i) {
// choose the person with smallest time to cross bridge
if (transferredMask & (1 << i)) {
if (minRow > timeToCross[i]) {
person = i;
minRow = timeToCross[i];
}
}
}

// now send this person to let and solve for smaller problem
res = timeToCross[person] + solveBridgeAndTorchProblem(mask|(1 << person),direction^1, timeToCross, dp);
}
else {

// __builtin_popcount() counts the bits in mask
for (int i=0;i<n;++i) {
// since there is only a single person on starting side, return him
res = timeToCross[i];
break;
}
}
}
else {

// find the minimum time by solving for each pair
res = INT_MAX;
for(int i=0;i<n;++i) {
// if ith person is not on right side, then do nothing
continue;
// else find another person and try to cross the bridge
for(int j=i+1;j<n;++j) {
// time to cross the bridge for current pair
int val = max(timeToCross[i], timeToCross[j]);
// solve for smaller subproblems
res = min(res, val);
}
}
}
}
}
}

int main()
{
int n;cin>>n;
vector<int> timeToCross(n);
for(int i=0;i<n;i++)cin>>timeToCross[i];
vector<vector<int>> dp(1<<20, vector<int>(2,-1));
cout << solveBridgeAndTorchProblem(mask, 0, timeToCross, dp);
return 0;
}
```
```5
25 6 5 8 4```
`54`

### 桥梁和火炬问题的Java代码

```import java.util.*;

class Main{

static int countBits(int n){
int nn = n;
int cnt = 0;
while(n>0){
if((n&1) == 1)
cnt++;
n = n/2;
}
n = nn;
return cnt;
}

static int solveBridgeAndTorchProblem(int mask, int direction, int timeToCross[], int dp[][])
{
int n = timeToCross.length;
// if nobody is left to transfer
return 0;

int res = 0;
// transfer people from left to right (from destination to start)
if(direction == 1) {
int minRow = Integer.MAX_VALUE, person=0;
for(int i = 0; i < n; ++i) {
// choose the person with smallest time to cross bridge
if((transferredMask & (1 << i)) > 0) {
if (minRow > timeToCross[i]) {
person = i;
minRow = timeToCross[i];
}
}
}

// now send this person to let and solve for smaller problem
res = timeToCross[person] + solveBridgeAndTorchProblem(mask|(1 << person),direction^1, timeToCross, dp);
}
else {

// countBits() counts the bits in mask
for (int i=0;i<n;++i) {
// since there is only a single person on starting side, return him
res = timeToCross[i];
break;
}
}
}
else {

// find the minimum time by solving for each pair
res = Integer.MAX_VALUE;
for(int i=0;i<n;++i) {
// if ith person is not on right side, then do nothing
continue;
// else find another person and try to cross the bridge
for(int j=i+1;j<n;++j) {
// time to cross the bridge for current pair
int val = Math.max(timeToCross[i], timeToCross[j]);
// solve for smaller subproblems
res = Math.min(res, val);
}
}
}
}
}
}

public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] timeToCross = new int[n];
for(int i=0;i<n;i++)
timeToCross[i] = sc.nextInt();
int dp[][] = new int[1<<20][2];
for(int i=0;i<(1<<20);i++){
dp[i][0] = -1;
dp[i][1] = -1;
}
}

}
```
```5
25 6 5 8 4```
`54`