「BZOJ1911」[Apio2010] 特别行动队commando
Description
Input
Output
Sample Input
4
-1 10 -20
2 2 3 4
-1 10 -20
2 2 3 4
Sample Output
9
HINT
题解
我发现似乎掌握了特殊的斜率优化技巧，我会假装四处看风景
dp方程：f[i]=max(f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c)
如果j>k且j比k更优
f[j]-f[k]+a*sum[j]^2-a*sum[k]^2+b*(sum[k]-sum[j])>2*a*(sum[j]-sum[k])*sum[i]
|
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 |
#include<iostream> #include<cstdio> #include<algorithm> #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return f*x; } int n,l,r; int a,b,c; int x[1000005]; ll sum[1000005],f[1000005]; int q[1000005]; inline ll sqr(ll x){return x*x;} inline double slop(int k,int j) {return (double)(f[j]-f[k]+a*(sqr(sum[j])-sqr(sum[k]))+b*(sum[k]-sum[j]))/(double)(2*a*(sum[j]-sum[k]));} int main() { n=read(),a=read(),b=read(),c=read(); for(int i=1;i<=n;i++)x[i]=read(); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+x[i]; for(int i=1;i<=n;i++) { while(l<r&&slop(q[l],q[l+1])<sum[i])l++; int t=q[l]; f[i]=f[t]+a*sqr(sum[i]-sum[t])+b*(sum[i]-sum[t])+c; while(l<r&&slop(q[r-1],q[r])>slop(q[r],i))r--; q[++r]=i; } printf("%lld",f[n]); return 0; } |
计数器 9856442
OI 课件=>
OI 课件=>
[…] 「BZOJ1911」[Apio2010] 特别行动队commando – 斜率优化 – hzwer.com […]
假装看风景可还行