_bzoj1911 [Apio2010]特别行动队【斜率优化dp】
2024-09-07 03:38:09
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1911
裸的斜率优化dp。
#include <cstdio> const int maxn = 1000005; int n, a, b, c, s[maxn], head, tail;
char ch;
long long f[maxn];
struct point {
long long x, y;
int id;
} que[maxn], tem; inline void readint(int & rt) {
while ((ch = getchar()) < 48);
rt = ch - 48;
while ((ch = getchar()) > 47) {
rt = rt * 10 + ch - 48;
}
}
inline long long poww(long long aa) {
return aa * aa;
} int main(void) {
//freopen("in.txt", "r", stdin);
readint(n);
scanf("%d%d%d", &a, &b, &c);
for (int i = 1; i <= n; ++i) {
readint(s[i]);
s[i] += s[i - 1];
}
int j;
que[tail++] = (point){0, 0, 0};
for (int i = 1; i <= n; ++i) {
while (tail - head > 1 && que[head].y - que[head + 1].y < 2 * a * s[i] * (que[head].x - que[head + 1].x)) {
++head;
}
j = que[head].id;
f[i] = f[j] + a * poww(s[i] - s[j]) + b * (long long)(s[i] - s[j]) + c;
tem = (point){s[i], f[i] + a * poww(s[i]) - b * (long long)s[i], i};
while (tail - head > 1 && (tem.y - que[tail - 1].y) * (que[tail - 1].x - que[tail - 2].x) > (que[tail - 1].y - que[tail - 2].y) * (tem.x - que[tail - 1].x)) {
--tail;
}
que[tail++] = tem;
}
printf("%lld\n", f[n]);
return 0;
}
最新文章
- SharePoint 2013 安装中间出错了怎么办? 每一次安装都是一段曲折的路【1603(0x643) 】
- SQL基础&;笔试题
- poj3249Test for Job(记忆化搜索)
- 从C#到Objective-C,循序渐进学习苹果开发(3)--分类(category)和协议Protocal的理解
- 总结XX网app中webapp常见的前端错误。
- IOS单例模式(Singleton)
- BZOJ 2016: [Usaco2010]Chocolate Eating
- dedecms的入门使用
- Bootstrap网站模板
- 关于sscanf函数的各种详细用法
- devexpress设置系统全局字体(含工具栏字体)
- poj1269计算几何直线和直线的关系
- springMVC--XML解析
- 在Servlet中获取spring容器WebApplicationContext
- Git使用详细教程(5):修改提交说明
- [转] 前后端分手大师——MVVM 模式
- 下载文件 utils
- 51nod-1459-迷宫游戏
- 手动卸载Office2010
- .Net Core 本地化&;全球化 实践