计蒜客|计蒜客 - 44284 Safe Passage(贪心、思维、dp).md 计蒜客-44284SafePassage(贪心、思

题目大意题目链接
很经典的问题。
n个人要过河，过河需要保护罩，一个保护罩最多只能容纳两个人，每个人过去都有花费的时间，如果两个人一起过，花费的总时间时间就是两个人中花费的时间最大的那个。
问怎么安排能尽快过河。
分析十分经典的问题，从小到大排序，充分利用好a[1], a[2]，一共有两种情况。
a[1], a[2] 过去， a[1]回来， a[i] 和 a[i - 1] 过去， a[2] 回来，总花费是a[2] + a[1] + a[i] + a[2].
【计蒜客|计蒜客 - 44284 Safe Passage(贪心、思维、dp).md】a[1]，a[i] 过去， a[1]回来，总花费是a[1] + a[i]
然后用dp！！， dp[i] 表示前i (包括i)全都过河花费的最小时间。
dp[i] = min(dp[i - 2] + a[2] + a[1] + a[i] + a[2] ,dp[i - 1] + a[1] + a[i])
代码

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

/* power by Solo_Dance */ #include #define eps 1e-8 using namespace std; #define ms(a, b) memset((a), (b), sizeof(a)) typedef long long ll; typedef unsigned long long ull; typedef pair P; const int N = 1e5 + 5; const int M = 1e6 + 5; const int INF = 0x3f3f3f3f; const ll ll_max = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 + 7; inline ll read() { ll res = 0; bool f = 0; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') f = 1; ch = getchar(); } while (ch <= '9' && ch >= '0') {res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); } return f ? (~res + 1) : res; } int a[100]; int f[100]; int main(){ int n = read(); for (int i = 1; i <= n; ++i) a[i] = read(); sort(a + 1, a + n + 1); f[1] = a[1], f[2] = a[2]; for (int i = 3; i <= n; ++i){ f[i] = min(f[i - 1] + a[1] + a[i], f[i - 2] + a[i] + 2 * a[2] + a[1]); } cout << f[n] << "\n"; return 0; }