斜率优化
# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <string.h>
# include <algorithm>
# define Sqr(x) (1LL * (x) * (x))
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
IL ll Read(){
RG char c = getchar(); RG ll x = 0, z = 1;
for(; c > '9' || c < '0'; c = getchar()) z = c == '-' ? -1 : 1;;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
return x * z;
}
const int MAXN(1000010);
int n, Q[MAXN], head, tail;
ll f[MAXN], sum[MAXN], a, b, c;
IL ll F(RG ll x){
return a * Sqr(x) + b * x + c;
}
IL double K(RG int i, RG int j){
RG ll x1 = 2 * a * sum[i], y1 = f[i] + a * Sqr(sum[i]) - b * sum[i];
RG ll x2 = 2 * a * sum[j], y2 = f[j] + a * Sqr(sum[j]) - b * sum[j];
return 1.0 * (y2 - y1) / (x2 - x1);
}
int main(){
n = Read(); a = Read(); b = Read(); c = Read();
for(RG int i = 1; i <= n; i++) sum[i] = sum[i - 1] + Read();
for(RG int i = 1; i <= n; i++){
while(head < tail && K(Q[head], Q[head + 1]) <= sum[i]) head++;
f[i] = f[Q[head]] + F(sum[i] - sum[Q[head]]);
while(head < tail && K(Q[tail - 1], Q[tail]) >= K(Q[tail], i)) tail--;
Q[++tail] = i;
}
printf("%lld\n", f[n]);
return 0;
}
APIO2010特别行动队的更多相关文章
-
BZOJ 1911: [Apio2010]特别行动队 [斜率优化DP]
1911: [Apio2010]特别行动队 Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 4142 Solved: 1964[Submit][Statu ...
-
【BZOJ 1191】 [Apio2010]特别行动队 (斜率优化)
dsy1911: [Apio2010]特别行动队 [题目描述] 有n个数,分成连续的若干段,每段的分数为a*x^2+b*x+c(a,b,c是给出的常数),其中x为该段的各个数的和.求如何分才能使得各个 ...
-
bzoj 1911 [Apio2010]特别行动队(斜率优化+DP)
1911: [Apio2010]特别行动队 Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 3191 Solved: 1450[Submit][Statu ...
-
BZOJ 1911: [Apio2010]特别行动队( dp + 斜率优化 )
sum为战斗力的前缀和 dp(x) = max( dp(p)+A*(sumx-sump)2+B*(sumx-sump)+C )(0≤p<x) 然后斜率优化...懒得写下去了... ------- ...
-
bzoj1911[Apio2010]特别行动队 斜率优化dp
1911: [Apio2010]特别行动队 Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 5057 Solved: 2492[Submit][Statu ...
-
P3628 [APIO2010]特别行动队(斜率优化dp)
P3628 [APIO2010]特别行动队 设$s[i]$为战斗力前缀和 显然我们可以列出方程 $f[i]=f[j]+a*(s[i]-s[j])^{2}+b*(s[i]-s[j])+c$ $f[i]= ...
-
[luogu P3628] [APIO2010]特别行动队
[luogu P3628] [APIO2010]特别行动队 题目描述 你有一支由 n 名预备役士兵组成的部队,士兵从 1 到 n 编号,要将他们拆分 成若干特别行动队调入战场.出于默契的考虑,同一支特 ...
-
【bzoj1911】[Apio2010]特别行动队
1911: [Apio2010]特别行动队 Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 4048 Solved: 1913[Submit][Statu ...
-
[APIO2010]特别行动队 --- 斜率优化DP
[APIO2010]特别行动队 题面很直白,就不放了. 太套路了,做起来没点感觉了. \(dp(i)=dp(j)+a*(s(i)-s(j))^{2}+b*(s(i)-s(j))+c\) 直接推出一个斜 ...
-
bzoj 1911: [Apio2010]特别行动队 -- 斜率优化
1911: [Apio2010]特别行动队 Time Limit: 4 Sec Memory Limit: 64 MB Description Input Output Sample Input 4 ...
随机推荐
-
百度Ueditor配置问题
var URL = window.UEDITOR_HOME_URL || getUEBasePath(); 在ueditor.config.js中这一句是配置编辑器的网站根目录位置的,建议不要改,网上 ...
-
C# 传值给C++
http://www.cnblogs.com/xumingming/archive/2008/10/10/1308248.html C#(.net)中的DllImport 大家在实际工作学习C# ...
-
redis——基础介绍
转自:http://www.cnblogs.com/xing901022/p/4863929.html 1 什么是Redis Redis(REmote DIctionary Server,远程数据字典 ...
-
nfs文件系统启动参数配置
1. tiny6410(增强版)bootargs(nfs文件挂载)启动参数(周学伟) noinitrd console=ttySAC0,115200 lcd=S70 init=/init root=/ ...
-
bzoj4316: 小C的独立集
Description 图论小王子小C经常虐菜,特别是在图论方面,经常把小D虐得很惨很惨. 这不,小C让小D去求一个无向图的最大独立集,通俗地讲就是:在无向图中选出若干个点,这些点互相没有边连接,并使 ...
-
[CODEVS1116]四色问题
题目描述 Description 给定N(小于等于8)个点的地图,以及地图上各点的相邻关系,请输出用4种颜色将地图涂色的所有方案数(要求相邻两点不能涂成相同的颜色) 数据中0代表不相邻,1代表相邻 输 ...
-
a^b%c 的三种形式
求a^b%c,(1 <= a,b <= 2^62, 1 <= c <= 10^9) 最主要的高速幂 _LL mod_exp(_LL a, _LL b, int c) { _L ...
-
开发者所需要知道的iOS7 SDK新特性
iOS 7 春风又绿加州岸,物是人非又一年.WWDC 2013 keynote落下帷幕,新的iOS开发旅程也由此开启.在iOS7界面重大变革的背后,开发者们需要知道的又有哪些呢.同去年一样,我会先简单 ...
-
使用VSFTPD传输文件
使用VSFTPD传输文件 一.文件传输协议 FTP(File Transfer Protocol)是一种在互联网进行文件传输的协议,基于B/S模式,默认使用20.21端口,其中20端口(数据端口)用于 ...
-
转://Oracle补丁及opatch工具介绍
一. CPU(Critical Patch Update) 一个CPU内包含了对多个安全漏洞的修复,并且也包括相应必需的非安全漏洞的补丁.CPU是累积型的,只要安装最新发布的CPU即可,其中包括之前发 ...