题意
本题和HDU 3507 Print Article如出一辙。都是给出了一个数列，和一个费用公式，要你设计一种把数列分为若干组之后计算出的总费用达到最小的方案。
思路
依然是斜率优化DP。不过本题有两个要点必须注意：1.我们默认炸毁了某一道路之后，就不要再去管默许炸毁了的道路之前的节点了。2.一定要注意DP数组的正确初始化（因为这个我挑通宵调试了近10小时）。
详细的状态转移方程还是建议自己推导，因为下标等微妙的细节稍有相左，就会产生错误，如果确信自己的方程没有问题不妨从上面几个要点调试。如果没有掌握斜率优化DP的基本知识，请移步HDU 3507 Print Article并仔细阅读教程。
代码
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
// // HDU2829.cpp // playground // // Created by Adam Chang on 2015/08/01. // Copyright © 2015年 Adam Chang. All rights reserved. // #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; const long long maxn = 1010; long long n, m; long long a[maxn], sum[maxn], sumul[maxn]; long long dp[2][maxn]; long long que[maxn], head, tail; long long slope_upper(long long l, long long b, long long a) { return (dp[l%2][a] - sumul[a] + sum[a] * sum[a]) - (dp[l%2][b] - sumul[b] + sum[b] * sum[b]); } long long slope_lower(long long b, long long a) { return sum[a] - sum[b]; } int main() { //freopen("testdata.hdub", "r", stdin); while (scanf("%lld%lld", &n, &m) != EOF) { if (n == 0 && m == 0) break; sum[0] = 0; sumul[0] = 0; for (long long i = 1; i <= n; ++i) { scanf("%lld", &a[i]); sum[i] = sum[i-1] + a[i]; sumul[i] = sumul[i-1] + sum[i-1] * a[i]; dp[0][i] = sumul[i]; } for (long long i = 1; i <= m; ++i) { head = tail = 0; que[tail++] = i; for (long long j = i+1; j <= n; ++j) { while (head + 1 < tail && slope_upper(i-1, que[head], que[head+1]) <= sum[j] * slope_lower(que[head], que[head+1])) { head++; } dp[i%2][j] = dp[(i-1)%2][que[head]] + sumul[j] - sumul[que[head]] - sum[que[head]] * (sum[j] - sum[que[head]]); while (head + 1 < tail && slope_upper(i - 1, que[tail-2], que[tail-1]) * slope_lower(que[tail-1], j) >= slope_lower(que[tail-2], que[tail-1]) * slope_upper(i - 1, que[tail-1], j)) { tail--; } que[tail++] = j; } } printf("%lld\n", dp[m%2][n]); } return 0; } |
