传送门
BZOJ
思路
设
fi
f
i
表示将
1∼i
1
∼
i
的士兵编队的最大战斗力，边界状态为
f0=0
f
0
=
0
，最终答案为
fn
f
n
，状态转移方程为：
fi=maxj<i{fj+a(Xi−Xj)2+b(Xi−Xj)+c}
f
i
=
max
j
<
i
{
f
j
+
a
(
X
i
−
X
j
)
2
+
b
(
X
i
−
X
j
)
+
c
}
其中
X
X
表示
x 的前缀和，时间复杂度为
O(n2)
O
(
n
2
)
。
大括号内展开得：
fj+aX2i−2aXiXj+aX2j+bXi−bXj+c
f
j
+
a
X
i
2
−
2
a
X
i
X
j
+
a
X
j
2
+
b
X
i
−
b
X
j
+
c
设
j>k
j
>
k
，若
j
j
比 k 更优，有：
fj+aX2i−2aXiXj+aX2j+bXi−bXj+c>fk+aX2i−2aXiXk+aX2k+bXi−bXk+c
f
j
+
a
X
i
2
−
2
a
X
i
X
j
+
a
X
j
2
+
b
X
i
−
b
X
j
+
c
>
f
k
+
a
X
i
2
−
2
a
X
i
X
k
+
a
X
k
2
+
b
X
i
−
b
X
k
+
c
化简：
(fj−fk)+(aX2j−aX2k)−(bXj−bXk)>2aXi(Xj−Xk)
(
f
j
−
f
k
)
+
(
a
X
j
2
−
a
X
k
2
)
−
(
b
X
j
−
b
X
k
)
>
2
a
X
i
(
X
j
−
X
k
)
由于
X
X
是 x 的前缀和，且
x>0
x
>
0
，所以可以除过来：
(fj−fk)+(aX2j−aX2k)−(bXj−bXk)Xj−Xk>2aXi
(
f
j
−
f
k
)
+
(
a
X
j
2
−
a
X
k
2
)
−
(
b
X
j
−
b
X
k
)
X
j
−
X
k
>
2
a
X
i
设为：
slope(j,k)>2aXi
s
l
o
p
e
(
j
,
k
)
>
2
a
X
i
设
j>k
j
>
k
，若
slope(j,k)>slope(k,l)
s
l
o
p
e
(
j
,
k
)
>
s
l
o
p
e
(
k
,
l
)
，则
k
k
永远不会是最优决策。
由于 2aXi 单调递减（不要忘了
a
a
<script type="math/tex" id="MathJax-Element-32">a</script> 是负数！），因此若不等式在某个时刻成立，那它将永远成立。故可以使用单调队列斜率优化。
参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
}
const LL INF = (~(LL(1) << (sizeof(LL) * 8 - 1))) >> 1;
const int maxn = int(1e6) + 5;
int n;
LL a, b, c;
LL x[maxn];
LL f[maxn];
inline LL DP(int i, int j)
{
register LL X = x[i] - x[j];
return f[j] + a * X * X + b * X + c;
}
#define RunInstance(x) delete new x
struct brute
{
brute()
{
f[0] = 0;
for (int i = 1; i <= n; i++)
{
LL& ans = f[i];
ans = -INF;
for (int j = 0; j < i; j++)
ans = std::max(ans, DP(i, j));
}
printOut(f[n]);
}
};
struct work
{
inline static double slope(int j, int k)
{
return (double)((f[j] - f[k]) + a * (x[j] * x[j] - x[k] * x[k]) -
b * (x[j] - x[k])) / (x[j] - x[k]);
}
int deque[maxn];
int head, tail;
work()
{
head = tail = 0;
f[0] = 0;
deque[tail++] = 0;
for (int i = 1; i <= n; i++)
{
while (tail - head > 1 && slope(deque[head + 1], deque[head]) > 2 * a * x[i])
head++;
f[i] = DP(i, deque[head]);
while (tail - head > 1 && slope(i, deque[tail - 1]) > slope(deque[tail - 1], deque[tail - 2]))
tail--;
deque[tail++] = i;
}
printOut(f[n]);
}
};
void run()
{
n = readIn();
a = readIn();
b = readIn();
c = readIn();
for (int i = 1; i <= n; i++)
x[i] = x[i - 1] + readIn();
RunInstance(work);
}
int main()
{
run();
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
