소객 보충제 이동 과정 중의 강

이주 과정 중의 하류

제목 링크

제목의 대의.

n명이 강을 건너야 하는데 사람마다 강을 건너는 시간이 있다. a[i], 매번 배에는 두 사람만 있고 한 배만 있다. 강을 건너는 시간은 배에 탄 사람의 강을 건너는 시간의 최대치에 따라 계산한다. 가장 짧은 시간에 강을 건널 수 있느냐고 묻는다.

문제풀이

할 줄 몰라요. 할 줄 몰라요.dp를 생각했는데 옮기지 않아요. 왜 앞뒤가 상관이 없는지 몰라서 dp를 생각하지 않았어요.이동: 분명히 매번 누군가가 사람을 데리러 돌아가야 하는데, 한 가지 상황은 가장 짧은 시간에 사람을 데리러 돌아가는 것이다.예를 들어 지금은 소모 시간에 따라 순서를 정했는데, 지금은 12가 지나갔다.그리고 하나, 둘, 셋, 넷, 둘, 셋.이 두 가지 상황, 이 두 가지 상황을 조합하면 모든 상황을 포함할 수 있다.그래서 코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include  
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
",dp[n]);
}```