斜率优化 – Tgotp-Blog

3437: 小P的牧场

令f[i]表示i点为控制站得最小花费。

f[n]即为答案,看到数据范围很明显会想到斜率优化。

那么按照一般套路化简可以得到

然后双端队列维护即可

c++代码如下:

 

4518: [Sdoi2016]征途

首先可以发现求得答案是 (∑(w - sum[n]/m)^2)/m * m * m

化简可得 (∑(w*m-w)^2)/m

容易列出方程f[i][j]表示在第i个人已经分了j块的最小方差。

即f[i][j] = min(f[j - 1][i - 1] + sum[i] - sum[[......]

Read more

1492: [NOI2007]货币兑换Cash

blog推荐:(因为自己不是很懂)

http://blog.csdn.net/clover_hxy/article/details/52490328

 

[bzoj1096][ZJOI2007]仓库建设

f[i]=min(f[j]+cal(j,i))

主要问题是如何在O1的时间内计算cal(j,i),即j+1到i这一段存入i所需的费用

我们可以利用前缀和的思想

sum[i]为p[i]的前缀和

如果所有物品都从0开始运到i,则费用为(sum[i]-sum[j])*x[i][......]

Read more

【bzoj1911】[Apio2010]特别行动队commando

首先读题后第一感觉这是个dp;

然后我们继续看到方程 =》一般来说这种题就可以用斜率优化了。

然后我们很容易推导得到f[i] = max(f[j]+a(s[i]-s[j])^2+b(s[i]-s[j])+c;

设k < j且j优于k;

即有:f[j]+a(s[i]-s[[......]

Read more

【bzoj1010】[HNOI2008]玩具装箱toy

 

【bzoj1597】[Usaco2008 Mar]土地购买

思路:斜率优化dp。

这种题一般自己推一推比较好;

简单的,我们可以看出,

首先:对于x排序,可以提出某些被包含的土地块(直接打包买)

然后:可以发现dp思路:f[i] = min(f[j]+b[j+1].y*b[i].x

但是可以很容易发现时间不够;

继续发现可[......]

Read more

3156: 防御准备

斜率优化

f[i] = min((i-j-1) * (i-j)/2 + f[j]) + data[i]

f[i] = min((i-1)* (i-j)/2 -j * (i-j)/2 + f[j]) + data[i]

f[i] = min(j -2*i*j+j*j + f[j]*2[......]

Read more