deque – Tgotp-Blog

【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

【bzoj1597】[Usaco2008 Mar]土地购买

思路:斜率优化dp。

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

简单的,我们可以看出,

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

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

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

继续发现可[……]

Read more