双头队列 – Tgotp-Blog

Luogu P2564&& BZOJ1293: [SCOI2009]生日礼物

 

1293: [SCOI2009]生日礼物

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2028  Solved: 1091
[Submit][Status][Discuss]

Description

小西有一条很长的彩带[……]

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