Input
第一行為一個整數N表示戰線的總長度。
第二行N個整數，第i個整數表示在位置i放置守衛塔的花費Ai。
Output
共一個整數，表示最小的戰線花費值。
Sample Input
10
2 3 1 5 4 5 6 3 1 2
Sample Output
18
HINT
1<=N<=10^6,1<=Ai<=10^9
?
這題還是裸的，就是先把輸入反向，然后就是斜率優化，這里注意的是那個，
每個反向后就可以以當前為最后一個了，這樣答案就不一定是f[n]了，每次計算一次，
在i這里建立最后一個的總花費，求出最小值。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #define ll long long 7 using namespace std; 8 9 const int NN=1e6+7; 10 11 int n,l,r; 12 int a[1000005],q[1000005]; 13 ll ans,f[1000005],sum[1000005];//這里f可以理解為最后建的小花費。 14 15 double slop(ll j,ll k) 16 { 17 return (f[j]-f[k]-sum[j]+sum[k]+j-k+j*j-k*k)/(double)(j-k);//這個式子比較好推 18 } 19 void init() 20 { 21 ans=1e16+7; 22 scanf("%d",&n); 23 for(int i=n;i>=1;i--) 24 scanf("%d",&a[i]); 25 for(int i=1;i<=n;i++) 26 sum[i]=sum[i-1]+i; 27 } 28 int main() 29 { 30 init(); 31 f[1]=a[1];q[1]=1;l=r=1;//開頭先放進去 32 ans=min(ans,f[1]+sum[n]-sum[1]-n+1);//不能遺漏每一種情況。 33 for(int i=2;i<=n;i++) 34 { 35 while(l<r&&slop(q[l],q[l+1])<i)l++; 36 int t=q[l]; 37 f[i]=f[t]+sum[i-1]-sum[t]-(ll)(i-t-1)*t+a[i]; 38 ans=min(ans,f[i]+sum[n]-sum[i]-(ll)(n-i)*i);//因為不一定要最后一個地方建木偶。 39 while(l<r&&slop(q[r-1],q[r])>slop(q[r],i))r--;//找下凸包。 40 q[++r]=i; 41 } 42 printf("%lld",ans); 43 }
?
