文档章节

【BZOJ3437】小P的牧场(动态规划,斜率优化)

o
 osc_odyg6b92
发布于 2018/07/13 16:00
字数 552
阅读 9
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

#【BZOJ3437】小P的牧场(动态规划,斜率优化) ##题面 BZOJ ##题解 考虑暴力$dp$,设$f[i]$表示强制在$i$处建立控制站的并控制$[1..i]$的最小代价。 很显然,枚举上一个控制站的位置$j$ $f[i]=min(f[j]+Calc(i,j)+a[i])$,其中$Calc(i,j)$表示$i,j$之间被$i$控制的位置产生的贡献。 这个可以用前缀和优化做到$O(1)$计算$Calc$ 预处理$s1[i]=\sum b[i],s2[i]=\sum (n-i+1)b[i]$ 那么$Calc(i,j)=s2[i]-s2[j]-(s1[i]-s1[j])(n-i+1)$ 考虑两个位置$j,k$,满足$k\lt j$,并且$k$的转移劣于$j$ 那么 $f[k]+Calc(i,k)\gt f[j]+Calc(i,j)$ 拆开之后是: $f[k]-s2[k]+s1[k](n-i+1)\gt f[j]-s2[j]+s1[j](n-i+1)$ 令$g[i]=f[i]-s2[i]+s1[i]*(n+1)$ 将所有项按照是否与$i$相关分类,可以得到 $(g[k]-g[j])\gt (s1[k]-s1[j])*i$ 因为$k<j$,所以$s1[k]<s1[j]$,除过去要变号 $$i>\frac{g[k]-g[j]}{s1[k]-s1[j]}$$ 妥妥的斜率优化,因为$i$单增,可以单调队列解决。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define RG register
#define MAX 1000100
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int n,a[MAX],b[MAX];
int Q[MAX],h,t;
ll f[MAX],s1[MAX],s2[MAX];
ll calc(int i,int j){return f[j]+s2[i]-s2[j]-(s1[i]-s1[j])*(n-i+1)+a[i];}
double Slope(int j,int k)
{
	double gj=f[j]-s2[j]+1.0*s1[j]*(n+1);
	double gk=f[k]-s2[k]+1.0*s1[k]*(n+1);
	return 1.0*(gj-gk)/(s1[j]-s1[k]);
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)a[i]=read();
	for(int i=1;i<=n;++i)b[i]=read();
	for(int i=1;i<=n;++i)s1[i]=s1[i-1]+b[i];
	for(int i=1;i<=n;++i)s2[i]=s2[i-1]+1ll*(n-i+1)*b[i];
	Q[h=t=1]=0;
	for(int i=1;i<=n;++i)
	{
		while(h<t&&Slope(Q[h],Q[h+1])<=i)++h;
		int j=Q[h];f[i]=calc(i,j);
		while(h<t&&Slope(Q[t],Q[t-1])>=Slope(Q[t-1],i))--t;
		Q[++t]=i;
	}
	printf("%lld\n",f[n]);
}

o
粉丝 1
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
性能优化工具--Starfish

Starfish 是一个用于大数据分析的自调优系统,这是一托管 Github 上的项目,但目前访问是 404,不清楚为何。Starfish 相当于是一个性能优化工具,可让 Hadoop 用户和应用达到最佳性能,包含三...

匿名
2012/11/24
722
0
基于OSSIM平台下华为交换机日志收集插件的开发

基于OSSIM平台下华为交换机日志收集插件的开发 长期以来,大家在收集华为交换机日志是往往通过syslog协议转发的方式,将华为交换机日志转发到日志收集器上,简单存储,但这样并没有将日志标准...

OSSIM
2016/03/04
335
2
web前端图片极限优化策略

  随着web的发展,网站资源的流量也变得越来越大。据统计,60%的网站流量均来自网站图片,可见对图片合理优化可以大幅影响网站流量,减小带宽消耗和服务器压力。 一、现有web图片格式 我们...

ouven
2016/01/05
1W
13
SQL优化(五) PostgreSQL (递归)CTE 通用表表达式

  原创文章,转载请务必将下面这段话置于文章开头处。   本文转发自Jason’s Blog,原文链接 http://www.jasongj.com/sql/cte/ CTE or WITH WITH语句通常被称为通用表表达式(Common Ta...

郭俊_Jason
2016/04/12
532
4
搞定编程大赛必知哪10个算法?

再没有比算法更让人头疼的东西了吧! 前两天参加了一个编程大赛http://www.ijiami.cn/newsInfo?id=519&v=2,有感于算法,所以整理了这篇关于编程竞赛的10个算法。 动态规划(DP)似乎占据了大...

小开2014
2014/10/22
396
6

没有更多内容

加载失败,请刷新页面

加载更多

如何在SQL Server中将多行文本合并为单个文本字符串?

问题: Consider a database table holding names, with three rows: 考虑一个包含名称的数据库表,该表具有三行: PeterPaulMary Is there an easy way to turn this into a single str......

富含淀粉
13分钟前
9
0
在JavaScript中生成特定范围内的随机整数? - Generating random whole numbers in JavaScript in a specific range?

问题: 如何可以生成两个指定的变量之间的随机整数在JavaScript中,例如x = 4和y = 8将输出任何的4, 5, 6, 7, 8 ? 解决方案: 参考一: https://stackoom.com/question/6PRz/在JavaScript中...

fyin1314
44分钟前
8
0
Vim清除最后一个搜索突出显示 - Vim clear last search highlighting

问题: Want to improve this post? 想要改善这篇文章吗? Provide detailed answers to this question, including citations and an explanation of why your answer is correct. 提供此问题......

技术盛宴
今天
23
0
马化腾每天刷 Leetcode?代码你打算写到几岁?

本文作者:o****0 前几天,一张未证真伪的截图流传,图中显示马化腾几乎每天都会在 Leetcode 上提交代码。 截图还贴出一个 Leetcode 账户地址。该地址的头像已从马化腾的照片换成腾讯 logo,...

百度开发者中心
前天
13
0
滴滴 3000+ Kylin Cube 背后的实践经验揭秘

本次分享主要有三个部分:Kylin 在滴滴的整体应用、架构的实践经验、滴滴全局字典最新版本的实现以及 Kylin 最新实时 OLAP 探索经验分享。 Kylin 在滴滴的应用&架构 Kylin 在滴滴的三类应用场...

浪尖聊大数据
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部