NC205464. 救治新冠肺炎患者
描述
输入描述
输入一行一个正整数n(1<=n<=3000).接下来一行n个整数，分别表示a1,a2,a3...an.(1<=ai<=1e9)
输出描述
输出一行一个整数,最优安排时死亡的人的总数.
示例1
输入:
6 40 200 1 300 2 10
输出:
1950
说明:
C++11(clang++ 3.9) 解法, 执行用时: 211ms, 内存消耗: 46816K, 提交时间: 2020-04-27 19:16:58
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, dp[3005][3005], dp2[3005], sum[3005], a[3005];
int main() {
scanf("%lld", &n);
for (ll i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
sum[i] = sum[i - 1] + a[i];
}
for (int i = 1; i <= n - 1; ++i)
for (int j = 1; j <= n - i; ++j)
dp[j][i + j] = dp[j + 1][i + j] + min((sum[i + j] - sum[j]) * 2,
a[j] * i * 3 + sum[i + j] - sum[j]);
memset(dp2, 0x3f, sizeof dp2);
dp2[0] = 0;
for (int i = 1; i <= n; ++i)
for (int j = 0; j < i; ++j)
dp2[i] = min(dp2[i], dp2[j] + dp[j + 1][i]
+ (4 * i - 4 * j - 2) * (sum[n] - sum[i]));
printf("%lld", dp2[n]);
return 0;
}