比较经典的斜率优化...
斜率优化相当于单调队列的升级版
主要针对的是a[i]*b[j]这一项的优化
对于可能决策的点 在坐标平面中可以表示成(b[j],f(j))这种形式
然后就是找一条合法斜率的直线使得截距最小
然后套用单调队列处理
写的时候可以选择把求斜率变成函数 这样main里面就套路一些
注意最后队列判空的时候因为要访问tail-1所以注意一下不要越界...
Code:
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 #include<vector> 6 #include<queue> 7 #define rep(i,a,n) for(int i = a;i <= n;++i) 8 #define per(i,n,a) for(int i = n;i >= a;--i) 9 #define inf 2147483647 10 #define ms(a,b) memset(a,b,sizeof a) 11 using namespace std; 12 typedef long long ll; 13 typedef double D; 14 ll read() { 15 ll as = 0,fu = 1; 16 char c = getchar(); 17 while(c < '0' || c > '9') { 18 if(c == '-') fu = -1; 19 c = getchar(); 20 } 21 while(c >= '0' && c <= '9') { 22 as = as * 10 + c- '0'; 23 c = getchar(); 24 } 25 return as * fu; 26 } 27 //head 28 const int N = 100005; 29 int n; 30 D s[N],a[N],dp[N],L; 31 D B(int i) {return a[i]+L+1;} 32 D x(int i) {return B(i);} 33 D y(int i) {return dp[i] + B(i)*B(i);} 34 D k(int i,int j) {return (y(j)-y(i))/(x(j)-x(i));} 35 int q[N]; 36 int main() { 37 n = read(),L = (D)read(); 38 rep(i,1,n) s[i] = s[i-1] + read(),a[i] = s[i] + i; 39 int h = 1,t = 1; 40 rep(i,1,n) { 41 while(h < t && k(q[h],q[h+1]) < 2 * a[i]) h++; 42 dp[i] = dp[q[h]] + (a[i] - B(q[h])) * (a[i] - B(q[h])); 43 while(h < t && k(i,q[t-1]) < k(q[t-1],q[t])) t--; 44 q[++t] = i; 45 } 46 printf("%lld ",(ll)dp[n]); 47 return 0; 48 }