迁徙过程中的河流
题目大意
有n个人要过河,每个人有过河的时间a[i],每次船上只能有两个人,只有一艘船,过河的时间按照船上的人的过河时间的最大值算,问最短多长时间可以过河?
题解
不会做,,不会
dp数组:dp[i] 前i个过河需要的最短时间。
想到了dp,但是不会转移 ,不知道为啥又感觉前后没有关系,就没想dp了。。
转移:
显然每次需要有人回去接人,
一种情况是耗时最短的回去接一个。
还有一种情况是:
比如 现在按耗时排序了,,现在1 2 已经过去了。然后 就可以 1回来 3 4过去2回来接1 。
就这两种情况,这两种情况组合下来可以包含所有情况。
所以代码:
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){
freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){
freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
a %= mod;ll ans = 1;while(b){
if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
bool operator()(const pii & a, const pii & b){
return a.second > b.second;}};
int lb(int x){
return x & -x;}
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+9;
const int maxn = 500 + 5;
ll dp[maxn];
ll a[maxn];
int main()
{
int n;
scanf("%d",&n);
for (int i = 1; i <= n; i ++ )
scanf("%lld",&a[i]);
sort(a + 1, a + 1 + n);
dp[1] = a[1];
dp[2] = a[2];
for (int i = 3; i <= n; i ++ )
{
dp[i] = min(dp[i - 1] + a[1] + a[i],dp[i - 2] + a[1] + a[i] + a[2] + a[2]);
}
printf("%lld\n",dp[n]);
}```