斜率优化 – Tgotp-Blog

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