BZOJ 1911: [Apio2010]特别行动队( dp + 斜率优化 )

BZOJ 1911: [Apio2010]特别行动队( dp + 斜率优化 )

sum为战斗力的前缀和

dp(x) = max( dp(p)+A*(sumx-sump)2+B*(sumx-sump)+C )(0≤p<x)

然后斜率优化...懒得写下去了...

--------------------------------------------------------------------------------

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 1000009;
 
int N, A, B, C, Q[maxn], qh, qt;
ll w[maxn], dp[maxn];
 
inline ll f(int x) {
return dp[x] + ll(A) * w[x] * w[x];
}
 
inline ll g(int x, int p) {
return dp[p] + ll(A) * (w[x] - w[p]) * (w[x] - w[p]) + ll(B) * (w[x] - w[p]) + C;
}
 
int main() {
scanf("%d%d%d%d", &N, &A, &B, &C);
w[0] = 0;
for(int i = 1; i <= N; i++) {
scanf("%d", w + i);
w[i] += w[i - 1];
}
qh = qt = 0;
Q[qt++] = 0;
dp[0] = 0;
for(int i = 1; i <= N; i++) {
ll t = 2LL * A * w[i] + B;
while(qt - qh >= 2 && f(Q[qh + 1]) - f(Q[qh]) > t * (w[Q[qh + 1]] - w[Q[qh]])) qh++;
dp[i] = g(i, Q[qh]);
while(qt - qh >= 2 && (ll) (f(i) - f(Q[qt - 1])) * (w[Q[qt - 1]] - w[Q[qt - 2]]) > (ll) (f(Q[qt - 1]) - f(Q[qt - 2])) * (w[i] - w[Q[qt - 1]])) qt--;
Q[qt++] = i;
}
printf("%lld\n", dp[N]);
return 0;
}

--------------------------------------------------------------------------------

1911: [Apio2010]特别行动队

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 2998  Solved: 1354
[Submit][Status][Discuss]

Description

BZOJ 1911: [Apio2010]特别行动队( dp + 斜率优化 )

Input

BZOJ 1911: [Apio2010]特别行动队( dp + 斜率优化 )

Output

BZOJ 1911: [Apio2010]特别行动队( dp + 斜率优化 )

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

9

HINT

BZOJ 1911: [Apio2010]特别行动队( dp + 斜率优化 )

Source

上一篇:[luogu P3628] [APIO2010]特别行动队


下一篇:开发一个基于 Android系统车载智能APP