【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[j])^2+b(s[i]-s[j])+c >= f[k]+a(s[i]-s[k])^2+b(s[i]-s[k])+c;

展开得到:(f[j]-f[k] + a*(pow(s[j])-pow(s[k]))+b*(s[k]-s[j]))/(2.0*a*(s[j]-s[k])) < s[i](这里复制的底下代码,懒得打了QAQ)

然后就套斜率优化就好了;

ok;

c++代码如下:

 

3 + 9 =