[APIO2010]特别行动队 --- 斜率优化DP
标签：斜率优化 ide tchar lap 技术 api soft ace define
[APIO2010]特别行动队
题面很直白，就不放了。
太套路了，做起来没点感觉了。
\(dp(i)=dp(j)+a*(s(i)-s(j))^{2}+b*(s(i)-s(j))+c\)
直接推出一个斜率优化的式子上单调队列就好了
时间/空间复杂度：\(O(n)\)
#include#define sid 1000500
#define ri register int
#define ll long long
#define dd double
using namespace std;
#define getchar() *S ++
char RR[30000005], *S = RR;
inline int read(){
int p = 0, w = 1;
char c = getchar();
while(c > ‘9‘ || c ‘0‘) {
if(c == ‘-‘) w = -1;
c = getchar();
}
while(c >= ‘0‘ && c ‘9‘) {
p = p * 10 + c - ‘0‘;
c = getchar();
}
return p * w;
}
ll dp[sid], sum[sid];
int q[sid], n, a, b, c;
#define x(g) (sum[(g)])
#define y(g) (dp[(g)] + a * sum[(g)] * sum[(g)] - b * sum[(g)])
inline dd s(int i,int j){
return (dd)(y(i) - y(j)) / (dd)(x(i) - x(j));
}
int main(){
fread(RR, 1, sizeof(RR), stdin);
n = read(); a = read();
b = read(); c = read();
for(ri i = 1; i 1] + read();
ri fr = 1, to = 1;
for(ri i = 1; i ){
while(fr + 1 1]) > 2 * a * sum[i]) fr ++;
int p = q[fr];
ll pp = sum[i] - sum[p];
dp[i] = dp[p] + a * pp * pp + b * pp + c;
while(fr + 1 1]) 1])) to --;
q[++ to]=i;
}
printf("%lld\n", dp[n]);
return 0;
}
特别行动队
[APIO2010]特别行动队 --- 斜率优化DP
标签：斜率优化 ide tchar lap 技术 api soft ace define
原文地址：https://www.cnblogs.com/reverymoon/p/8983179.html
评论