BZOJ3437 小P的牧场 && SDOI2016 征途 斜率优化

发布于 2017-06-15  2.34k 次阅读


BZOJ3437: 小P的牧场

[toggle hide="yes" title="题目" color=""]
Description

小P在MC里有n个牧场,自西向东呈一字形排列(自西向东用1…n编号),于是他就烦恼了:为了控制这n个牧场,他需要在某些牧场上面建立控制站,每个牧场上只能建立一个控制站,每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场(它西边第一个控制站所在的牧场不被控制)(如果它西边不存在控制站,那么它控制西边所有的牧场),每个牧场被控制都需要一定的花费(毕竟在控制站到牧场间修建道路是需要资源的嘛~),而且该花费等于它到控制它的控制站之间的牧场数目(不包括自身,但包括控制站所在牧场)乘上该牧场的放养量,在第i个牧场建立控制站的花费是ai,每个牧场i的放养量是bi,理所当然,小P需要总花费最小,但是小P的智商有点不够用了,所以这个最小总花费就由你来算出啦。

Input

第一行一个整数 n 表示牧场数目

第二行包括n个整数,第i个整数表示ai

第三行包括n个整数,第i个整数表示bi

 

Output

只有一行,包括一个整数,表示最小花费

Sample Input
4
2 4 2 4
3 1 4 2
Sample Output
9
样例解释
选取牧场1,3,4建立控制站,最小费用为2+(2+1*1)+4=9。
1<=n<=1000000, 0 < a i ,bi < = 10000

[/toggle]

这题思路十分清奇,我一开始推了个正常的DP式子,大力化简,发现无论如何也化不出来斜率优化的形式,去看了题解才知道是要逆向思维:因为每个控制站都只能控制当前点和左边的点,所以n号点一定要放。因此可以设f[i]为在n-1~i中新增控制点i所能节省的最大费用,f[i]=max{f[j]+sum[i]*(j-i)}+a[i]。剩下的就是斜率的套路了。

 

[toggle hide="yes" title="代码" color=""]

[/toggle]

 


 

[SDOI2016 Round1]征途

[toggle hide="yes" title="题目" color=""]
Description

Pine开始了从S地到T地的征途。
从S地到T地的路可以划分成n段,相邻两段路的分界点设有休息站。
Pine计划用m天到达T地。除第m天外,每一天晚上Pine都必须在休息站过夜。所以,一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。
帮助Pine求出最小方差是多少。
设方差是v,可以证明,v×m^2是一个整数。为了避免精度误差,输出结果时输出v×m^2。

Input

第一行两个数 n、m。
第二行 n 个数,表示 n 段路的长度

Output

 一个数,最小方差乘以 m^2 后的值

Sample Input

5 2
1 2 5 8 6

Sample Output

36

HINT

1≤n≤3000,保证从 S 到 T 的总路程不超过 30000

[/toggle]

这道题先得把要求的结果化简一下,大力化简,得ans=min(m*∑a[i]^2)-sum^2。其中a[i]表示第i天所走路程。问题转化为最小化∑a[i]^2。设f[i][j]:前i天走了前j块的最小∑a[i]^2,则f[i][j]=min(f[i-1][k]+(s[j]-s[k])^2),设g(a,b)=f[i-1][a]-f[i-1][b]+s[a]^2-s[b]^2,h(a,b)=2*(s[a]-s[b]),则若a<b且a比b优,g(a,b)/h(a,b)<s[j],接下来就是套路了。

 

 

[toggle hide=yes" title="代码" color=""]

 

[/toggle]


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974