我的第一题斜率优化，没看题解就A了，高兴啊^O

拿到这题一开始我的想法是根据二次函数的对称性来贪心解决，后来发现这样不仅难以实现而且有严重的BUG。

随后就想到了DP，十分朴素的DP：用f[i]表示前i个队员分组后的最大值，那么可以枚举j，使得j+1..i为一组，计算其中的最大值。

令S[i] = a[1]+...+a[i]，以及calc(x) = Ax^2+Bx+C
f[i] = max{f[j]+calc(S[i]-S[j])   0 <= j < i

经实验证明，这么做可以拿到30分。

所以考虑一下优化。如果能在决策的时候，也就是选取j的时候，能够在O(1)的时间内完成，那么总体的复杂度就由O(n^2)降至O(n)。

转化

我们考虑一下j1和j2这两个决策，如果决策j2比j1好，那么就有：

 f[j1]+A*S[j1]*S[j1]-2*A*S[i]*S[j1]-B*S[j1]

如果我们令
C[i] = 2*A*S[i],
x    = S[j]
y    = f[j]+A*S[j]*S[j]-B*S[j]
那么上面那个不等式就可以简化成：
                     -C[i]x1+y1 < -C[i]x2+y2
slope(j1, j2) = (y2-y1)/(x2-x1) > C[i]
也就是说，只要slope(j1, j2) > C[i]那么j2就比j1好；反之slope(j1, j2) < C[i]那么j1就比j2好。
slope！斜率优化！用单调队列维护即可。怎么维护呢？

取头还是取尾？

我们考虑i2 > i，由于A < 0，因此C[i2] < C[i]，故如果j2比j1优：
slope(j1, j2) > C[i] > C[i2]
也就是说，j1不仅现在不比j2优，以后也没有翻身的机会了，故j1可以很果断的扔掉。这样一来，我们保证队列里面的j满足（其实队列里面存的都是备胎）：
slope(j1, j2) <= C[i]
slope(j2, j3) <= C[i]
...
slope(j_x-1, j_x) <= C[i]
由上面知道，j1比j2好，j2比j3好…… 故我们做到i时就应该取队列头部的决策。

单调性？

对于即将加进来的决策j3，我们假设
slope(j1, j2) < slope(j2, j3)
如果j2为最好的答案，那么必须满足：
slope(j1, j2) > C[i]
slope(j2, j3) <= C[i]
这显然与假设矛盾，所以我们可以得到：
   slope(j1, j2) >= slope(j2, j3) >= ...
 >= slope(j_n, j_n+1)
也就是说，这个队列是单调不上升的（其实那个等号取不取问题不是很大，也就是说单调递减也是一样的）

实现？

for i:=1 to n do 
    维护队头满足slope(head, head+1) <= C[i]
    f[i] = f[tail]+calc(sum[i]-sum[tail])
    维护队尾满足slope(tail-1, tail) >= slope(tail, i)
    i入队尾
2012.04.22 20:00UPDATE:我发现可以不求斜率，直接用前面的不等式来判断，进行入队出队即可。由于不用考虑浮点数除法（是的，下面的程序slope没有用double，是菜过的），因此速度快很多。再Cena上快了0.6s，bzoj上快了400ms（Cena测时间不准），所以其实应该看代码二。

代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <deque>
#include <algorithm>

const int MAX(1000000);
int n, a[MAX+1], sum[MAX+1];
long long A, B, C, f[MAX+1];
std::deque<int> Q;
inline long long calc(const long long x) { return A*x*x+B*x+C; }
inline long long slope(const int j1, const int j2)
{
  const long long y1 = f[j1]+A*sum[j1]*sum[j1]-B*sum[j1];
  const long long y2 = f[j2]+A*sum[j2]*sum[j2]-B*sum[j2];
  return (y2-y1)/(sum[j2]-sum[j1]);
}

int main()
{
  freopen("commando.in", "r", stdin);
  freopen("commando.out", "w", stdout);

  scanf("%dn%I64d %I64d %I64d", &n, &A, &B, &C);
  for (int i = 1; i <= n; ++i)
  {
    scanf("%d", a+i);
    sum[i] = sum[i-1]+a[i];
  }
  Q.push_back(0);
  for (int i = 1; i <= n; ++i)
  {
    while (Q.size() >= 2 && slope(Q.front(), *(Q.begin()+1)) > 2*A*sum[i]) Q.pop_front();
    f[i] = f[Q.front()]+calc(sum[i]-sum[Q.front()]);
    while (Q.size() >= 2 && slope(*(Q.rbegin()+1), Q.back()) < slope(Q.back(), i)) Q.pop_back();
    Q.push_back(i);
  }
  printf("%I64d", f[n]);

  fclose(stdin);fclose(stdout);
}




PS.其实我很纠结那个%I64d，因为我是Linux的，得用%lld，而Cena在Windows上，得用%I64d……用流的话又太慢了，即使是写了std::ios::sync_with_stdio(false);也一样

代码二



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <deque>
#include <algorithm>

const int MAX(1000000);
int n, a[MAX+1], sum[MAX+1];
long long A, B, C, f[MAX+1];
std::deque<int> Q;
inline long long calc(const long long x) { return A*x*x+B*x+C; }
inline bool invaild_head(const int i, const int j1, const int j2)
{
  const long long y1 = f[j1]+A*sum[j1]*sum[j1]-B*sum[j1];
  const long long y2 = f[j2]+A*sum[j2]*sum[j2]-B*sum[j2];
  return (sum[j2]-sum[j1])*2*A*sum[i] < y2-y1;
}
inline bool invaild_tail(const int i, const int j1, const int j2, const int j3)
{
  const long long y1 = f[j1]+A*sum[j1]*sum[j1]-B*sum[j1];
  const long long y2 = f[j2]+A*sum[j2]*sum[j2]-B*sum[j2];
  const long long y3 = f[j3]+A*sum[j3]*sum[j3]-B*sum[j3];
  return (y2-y1)*(sum[j3]-sum[j2]) < (y3-y2)*(sum[j2]-sum[j1]);
}

int main()
{
  scanf("%dn%lld %lld %lld", &n, &A, &B, &C);
  for (int i = 1; i <= n; ++i)
  {
    scanf("%d", a+i);
    sum[i] = sum[i-1]+a[i];
  }
  Q.push_back(0);
  for (int i = 1; i <= n; ++i)
  {
    while (Q.size() >= 2 && invaild_head(i, Q.front(), *(Q.begin()+1))) Q.pop_front();
    f[i] = f[Q.front()]+calc(sum[i]-sum[Q.front()]);
    while (Q.size() >= 2 && invaild_tail(i, *(Q.rbegin()+1), Q.back(), i)) Q.pop_back();
    Q.push_back(i);
  }
  printf("%lld", f[n]);
}