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 ;
}

最新文章

  1. 【已更新】【原创】Chrome53 最新版惊现无厘头卡死 BUG!
  2. Inverted sentences
  3. 多线程爬取 threading.Thread 文件名支持gbk编码
  4. CSS垂直三列居中,中间自适应
  5. hydra爆破用法
  6. BZOJ2789 : [Poi2012]Letters
  7. Android 禁用以及捕捉home键
  8. http://blog.csdn.net/wxwzy738/article/details/16968767
  9. 阿里云CentOS6.3 安装MongoDB教程
  10. poj 1840 Eqs (hash)
  11. 千呼万呼使出来Gogland (jetBrains发布的golang IDE)
  12. RabbitMQ 学习笔记
  13. Java多线程的创建与简单使用
  14. 腾讯云centos7.2安装宝塔面板和LAMP
  15. BZOJ.2324.[ZJOI2011]营救皮卡丘(费用流 Floyd)
  16. Linux_x86下NX与ASLR绕过技术
  17. Netty权威指南(笔记一)
  18. itext7知识点研究(PDF编辑)
  19. 基于Docker+Prometheus+Grafana监控SpringBoot健康信息
  20. gradle下载的依赖包位置 及 修改

热门文章

  1. selenium并行的使用
  2. 只为更快、更省、更安全的 Azure CDN
  3. 关于 no device found for connection ‘ System eth0′问题
  4. ABAP的include关键字,Java的import, C的include和C4C ABSL 的import比较
  5. 1923. Scary Politics (timus) (dfs) search
  6. Javascript作业—数组去重(要求:原型链上添加函数)
  7. 注解@Component,@Controller,@Service,@Repository简单了解
  8. U盘装CentOS6.4
  9. List&lt;T&gt;转换为二维数组
  10. java基础必备单词讲解 day two