显然的dp
转移方程中出现平方级式子
斜率优化之
#include<iostream> #include<cstdio> #include<queue> #include<vector> #include<bitset> #include<algorithm> #include<cstring> #include<map> #include<stack> #include<set> #include<cmath> #include<ext/pb_ds/priority_queue.hpp> using namespace std; const int maxn = 1E6 + 10; typedef long long LL; typedef double DB; int n,head,tail,q[maxn]; LL a,b,c,f[maxn],sum[maxn]; DB bx; DB F(int j,int k,int i) { LL A = (f[j] - f[k] + a*(2LL*sum[i] - sum[j] - sum[k])*(sum[k] - sum[j])); LL B = (sum[j] - sum[k]); return (DB)(A)/(DB)(B); } void Solve(int j,int i) { f[i] = f[j] + a*(sum[i] - sum[j])*(sum[i] - sum[j]) + b*(sum[i] - sum[j]) + c; } int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif cin >> n >> a >> b >> c; bx = b; for (int i = 1; i <= n; i++) { int x; scanf("%d",&x); sum[i] = x; sum[i] += sum[i-1]; } head = 1; tail = 0; for (int i = 1; i <= n; i++) { while (tail - head > 0 && F(q[tail-1],q[tail],i) < F(q[tail],i-1,i)) --tail; q[++tail] = i-1; while (tail - head > 0 && F(q[head],q[head+1],i) >= bx) ++head; Solve(q[head],i); } cout << f[n]; return 0; }
