[HDU][ACM]3507 Print Article
海胖子 - 2015/11/10题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=3507
题目大意
给定n个数,找到一个序列,使得 [sigma(1, k)Ci^2] + M 最小。
题解
[sigma(1, k)Ci^2] + M
Sk = sigma(1, i)Ci
f[i] = min{f[j] + (s[i] - s[j])^2 + M}
g[pos] = f[pos] + (s[i] - s[pos])^2 + M
when j < k, if g[k] better than g[j] then g[k] < g[j]
so g[pos] = f[pos] + (s[i] - s[pos])^2 + M
=> f[k] + (s[i] - s[k])^2 + M < f[k] + (s[i] - s[k])^2 + M
=> f[k] - f[j] + s[k]^2 - s[j]^2 < 2*s[i]*(s[k] - s[j])
as we know s[k] > s[j], so
=> (f[k] - f[j] + s[k]^2 - s[j]^2)/(s[k] - s[j]) < 2*s[i]
=> (f[j] - f[k] + s[j]^2 - s[k]^2)/(s[j] - s[k]) < 2*s[i]
so the left part is slope[j, k] = (f[j] - f[k] + s[j]^2 - s[k]^2)/(s[j] - s[k])
now we know when j < k, if k better then j then slope[j, k] < 2*s[i], or vice versa
after that we consider three point j, k, l, when j < k < l
if slope[j, k] > slope[k, l] then:
1. if slope[k, l] < 2*s[i] then l is better than k
2. if slope[k, l] > 2*s[i] then slope[j, k] > 2*s[i] too, so j is no worse then k
In summary, if slope[j, k] > slope[k, l] then k is useless
代码
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <string> #include <cctype> #include <climits> #include <queue> #include <set> #include <stack> #include <vector> #include <map> #include <algorithm> //#pragma comment(linker,"/STACK:102400000,102400000") using namespace std; /* quick input */ template <class T> bool scan_d(T &ret){ char c; int sgn; T bit = 0.1; if (c = getchar(), c == EOF) return 0; while (c != '-' && c != '.' && (c < '0' || c > '9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0' && c <= '9') ret = ret*10 + (c - '0'); if (c == ' ' || c == '\n') { ret *= sgn; return 1; } while (c = getchar(), c >= '0' && c <= '9') { ret += (c - '0')*bit; bit /= 10; } ret *= sgn; return 1; } /* end - quick input */ const int N = 500000; const long long inf = 1LL<<63; long long f[N + 5], s[N + 5]; int q[N + 5]; long long slope(int j, int k) { if (s[j] == s[k]) { if (f[j] >= f[k]) return -inf; return inf; } return (f[j] - f[k] + s[j]*s[j] - s[k]*s[k])/(s[j] - s[k]); } int main() { int n, m; while (scanf("%d%d", &n, &m) != EOF) { s[0] = 0; for (int i = 1; i <= n; ++i) { long long c; scanf("%lld", &c); s[i] = s[i - 1] + c; } int head = 0, tail = 0; f[0] = 0; q[0] = 0; for (int i = 1; i <= n; ++i) { while (head < tail && slope(q[head], q[head + 1]) < 2*s[i]) ++head; f[i] = f[q[head]] + (s[i] - s[q[head]])*(s[i] - s[q[head]]) + (long long)m; while (head < tail && slope(q[tail - 1], q[tail]) > slope(q[tail], i)) --tail; q[++tail] = i; } printf("%lld\n", f[n]); } return 0; }
转载保留版权:http://haipz.com/blog/i/6519 - 海胖博客
海胖,学计算机的吗
对啊,计算机科学与技术。