3437: 小P的牧场
2024-08-29 05:01:18
3437: 小P的牧场
思路
斜率优化。
dp[i]表示到第i个点(第i个点按控制台)的最小代价。
代码
#include<cstdio>
#include<iostream> using namespace std;
typedef long long LL; const int N = ;
LL f[N],s[N],a[N],b[N];
int q[N],L,R; inline int read() {
int x = ,f = ;char ch = getchar();
for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-;
for (; isdigit(ch); ch=getchar()) x = x*+ch-'';
return x * f;
}
double Slope(int i,int j) {
return 1.0*(f[i]+s[i]-f[j]-s[j])/(1.0*(b[i]-b[j]));
}
int main() {
int n = read();
for (int i=; i<=n; ++i) a[i] = read();
for (int i=; i<=n; ++i) {
b[i] = read();
s[i] = s[i-] + 1ll * b[i] * i;
b[i] += b[i-]; // 顺序不能反!
}
int L = ,R = ;
q[] = ;
for (int i=; i<=n; ++i) {
while (L<R && Slope(q[L],q[L+]) < (double)i) L++;
int j = q[L];
f[i] = f[j] + i * (b[i-] - b[j]) - (s[i-] - s[j]) + a[i];
while (L<R && Slope(q[R-],q[R]) > Slope(q[R],i)) R--;
q[++R] = i;
}
cout << f[n];
return ;
}
最新文章
- 【已更新】【原创】Chrome53 最新版惊现无厘头卡死 BUG!
- Inverted sentences
- 多线程爬取 threading.Thread 文件名支持gbk编码
- CSS垂直三列居中,中间自适应
- hydra爆破用法
- BZOJ2789 : [Poi2012]Letters
- Android 禁用以及捕捉home键
- http://blog.csdn.net/wxwzy738/article/details/16968767
- 阿里云CentOS6.3 安装MongoDB教程
- poj 1840 Eqs (hash)
- 千呼万呼使出来Gogland (jetBrains发布的golang IDE)
- RabbitMQ 学习笔记
- Java多线程的创建与简单使用
- 腾讯云centos7.2安装宝塔面板和LAMP
- BZOJ.2324.[ZJOI2011]营救皮卡丘(费用流 Floyd)
- Linux_x86下NX与ASLR绕过技术
- Netty权威指南(笔记一)
- itext7知识点研究(PDF编辑)
- 基于Docker+Prometheus+Grafana监控SpringBoot健康信息
- gradle下载的依赖包位置 及 修改
热门文章
- selenium并行的使用
- 只为更快、更省、更安全的 Azure CDN
- 关于 no device found for connection ‘ System eth0′问题
- ABAP的include关键字,Java的import, C的include和C4C ABSL 的import比较
- 1923. Scary Politics (timus) (dfs) search
- Javascript作业—数组去重(要求:原型链上添加函数)
- 注解@Component,@Controller,@Service,@Repository简单了解
- U盘装CentOS6.4
- List<;T>;转换为二维数组
- java基础必备单词讲解 day two