首页 > 代码库 > BZOJ3156 防御准备
BZOJ3156 防御准备
我去什么破题跳调了我一个半小时。
不是裸的斜率优化吗。。。我去我去我去我去我去我去！
首先我们倒着读进来，然后就省略了倒过来做的问题。
然后写出DP方程：
令f[i]表示选i作为塔时1到i的总代价，则
f[i] = min(f[j] + w(i, j) + a[i]) 其中有j < i 且 w(i, j) = (j - i - 1) * (j - i) / 2
整理可得到f[i] = g[j] + cost[i] - i * j的形式，于是
斜率优化即可。然后沙茶的我就开始了调程序之旅~~~我去。
1 /************************************************************** 2 Problem: 3156 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:1532 ms 7 Memory:28152 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 13 using namespace std;14 typedef long long ll;15 const int N = 1000005;16 ll a[N], f[N], g[N], ans;17 int n, l, r, q[N];18 19 inline int read(){20 int x = 0;21 char ch = getchar();22 while (ch < ‘0‘ || ch > ‘9‘)23 ch = getchar();24 while (ch >= ‘0‘ && ch <= ‘9‘){25 x = x * 10 + ch - ‘0‘;26 ch = getchar();27 }28 return x;29 }30 31 inline ll calc_f(ll i, ll x){32 return (ll) g[x] + a[i] - i * x * 2 + (i - 1) * i;33 }34 35 inline ll calc_g(ll x){36 return (ll) f[x] + x * (x + 1);37 }38 39 inline ll calc_ans(ll x){40 return (ll) f[x] + (n - x) * (n - x + 1);41 }42 43 bool pop_head(ll i){44 ll x = q[l], y = q[l + 1];45 return ((ll) i * (y - x) * 2 >= (ll) g[y] - g[x]);46 }47 48 bool pop_tail(ll i){49 ll x = q[r - 1], y = q[r];50 return ((ll) (g[i] - g[y]) * (y - x) < (ll) (g[y] - g[x]) * (i - y));51 }52 53 int main(){54 n = read();55 for (int i = n; i; --i)56 a[i] = read() << 1;57 f[1] = a[1], g[1] = calc_g(1), ans = calc_ans(1);58 q[1] = l = r = 1;59 for (int i = 2; i <= n; ++i){60 while (l < r && pop_head(i)) ++l;61 f[i] = calc_f(i, q[l]);62 g[i] = calc_g(i);63 ans = min(ans, calc_ans(i));64 while (l < r && pop_tail(i)) --r;65 q[++r] = i;66 }67 printf("%lld\n", ans >> 1);68 return 0;69 }
（p.s. rank3是我小号~~rank4是我自己，还是蛮快滴！Oh耶）
BZOJ3156 防御准备
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。