3156: 防御准备
Time Limit: 10 Sec Memory Limit: 512 MB Submit: 2361 Solved: 997 [ ][ ][ ]Description
Input
第一行为一个整数N表示战线的总长度。
第二行N个整数，第i个整数表示在位置i放置守卫塔的花费Ai。
Output
共一个整数，表示最小的战线花费值。
Sample Input
10 2 3 1 5 4 5 6 3 1 2
Sample Output
18
HINT
1<=N<=10^6,1<=Ai<=10^9
Source
分析：为了方便处理，将a序列翻转过来，那么题目就变成了从左往右处理.
首先很容易能想到这道题要用到斜率优化，why? 想象一下，枚举一个点i,如果当前点y要放木偶，总得在前面找一个位置放守望塔吧，那么这就是O(n^2)的了，朴素dp的复杂度都是如此，需要对此优化，如何优化，那就是斜率dp咯.
我一开始想的状态是f[i][0/1]表示前i个位置中，第i个位置放守望塔还是木偶的最小花费值. 可以转移，但这不是斜率优化的那种式子啊......
斜率优化要求一维的状态，那我的后面一个状态能不能去掉呢？如果令f[i]表示前i个位置中，第i个位置放守望塔的最小化费值，可以枚举前面一个放守望塔的位置j,在j+1 到 i-1之间都放木偶，这个答案是能够计算出来的.
f(i) = min{f(j) + sum[i - 1] - sum[j] - (i - 1 - j) * d[j] + a[i]}. d[i]表示i到1的距离,sum[i]表示d数组的前缀和，a[i]表示建守望塔的花费.
然后就是斜率优化的常规套路了. 注意这里要求min,求的是上凸壳，别弄反了！
#include#include #include #include using namespace std;typedef long long ll;const ll maxn = 1000010;ll n,a[maxn],l,r,f[maxn],q[maxn],sum[maxn],d[maxn],ans;ll K(ll i){ return -d[i];}ll B(ll i){ return i * d[i] + f[i] - sum[i];}ll Y(ll i,ll j){ return K(i) * (j - 1) + B(i);}bool cmp(ll y1,ll y2,ll y3){ ll temp1 = (K(y1) - K(y3)) * (B(y2) - B(y1)); ll temp2 = (K(y1) - K(y2)) * (B(y3) - B(y1)); return temp1 >= temp2;}int main(){ scanf("%lld",&n); for (ll i = 1; i <= n; i++) scanf("%lld",&a[i]); for (int i = 1, j = n; i <= j; i++,j--) swap(a[i],a[j]); d[1] = 0; for (ll i = 2; i <= n; i++) d[i] = d[i - 1] + 1; for (ll i = 1; i <= n; i++) sum[i] = sum[i - 1] + d[i]; f[1] = a[1]; q[r] = 1; for (ll i = 2; i <= n; i++) { while (l < r && Y(q[l],i) >= Y(q[l + 1],i)) l++; f[i] = Y(q[l],i) + sum[i - 1] + a[i]; while (l < r && cmp(i,q[r - 1],q[r])) r--; q[++r] = i; } ans = f[n]; for (ll i = 1; i < n; i++) ans = min(ans,f[i] + sum[n] - sum[i] - d[i] * (n - i)); printf("%lld\n",ans); return 0;}