[TIOJ] 1745. [APIO '10] Commando

題目連結:http://tioj.infor.org/problems/1745

---

這題應該不難想到DP的方式\[ f(x) =ax^2+bx+c \\ dp[i] = \max_{0 \leq j < i}(f(\sum_{k=i+1}^{j}arr[k]) + dp[j]) \]，但是也不難發現它的複雜度會是$O(n^2)$。這時就要優化他，可以發現它可以套用斜率優化，因為對轉移式做一些移項跟變數變換後會變成\[ S_i = \sum_{j=0}^{i} arr[j]\\ dp[i] = \max_{0 \leq j < i}(-2aS_j \cdot S_i + a{S_j}^2 - bS_j + dp[j]) + a{{S_i}^2} + bS_i + c \]那很明顯的可以發現若把j看成是定值，i看成是變數的話，就會發現max裡面那一坨就是一個一次函數，而且斜率會隨j增加而增加。然後我們會發現自己每次在轉移時都會比之前多一項j，所以其實可以看成每次轉移時加入一條線(或每次轉移後加入一條線)，並且會發現當這條線(也就是這個j)，已經有比他新的線比他好時，那他就不會被轉移到，此外，如果有些線在超越比他新的線前，已經被某條更新的線超越，則他也不會是可以拿來轉移的。有了這幾個性質，我們就可以發現要判斷有沒有新的線比他好，就等價於在一個deque中(裡面存著所有先前可以轉移的線)，比較他的前兩個元素，如果第一項在帶入i時會比較小，那他就符合前面所說的第一種情況，可以被移除；第二種情況則是在將當前的線放入deque時，比較pos1(最末項跟當前項的交點)與pos2(最末項跟次末項的交點的x座標)，如果pos1 < pos2，那最末的那條線就可以砍掉。發現每條線只會進deque一次，出一次，所以複雜度就壓到$O(n)$了

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define INF 2147483647
#define N 1000000

lld a,b,c;
lld arr[N+5], sm[N+5], dp[N+5];
inline bool detectBeyond(int,int,int);
inline lld f(int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;
	cin>>a>>b>>c;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		sm[i]=arr[i]+sm[i-1];
	}
	for(int i=1;i<=n;i++)dp[i]=-INF;
	deque<int> dq;
	dq.push_back(0);
	for(int i=1;i<=n;i++){
		while(dq.size()>1 && f(dq[0], i) < f(dq[1], i)) dq.pop_front();
		dp[i] = f(dq[0], i) + a*sm[i]*sm[i]+b*sm[i]+c;
		while(dq.size()>1  && detectBeyond(dq[dq.size()-2], dq[dq.size()-1], i)) dq.pop_back();
		dq.push_back(i);
	}
	cout<<dp[n]<<'\n';
	return 0;
}
inline bool detectBeyond(int i, int j, int k){
	lld ai = -2*a*sm[i], bi=a*sm[i]*sm[i]-b*sm[i]+dp[i];
	lld aj = -2*a*sm[j], bj=a*sm[j]*sm[j]-b*sm[j]+dp[j];
	lld ak = -2*a*sm[k], bk=a*sm[k]*sm[k]-b*sm[k]+dp[k];
	return (bj-bi)*(aj-ak) >= (ai - aj)*(bk - bj);
}
inline lld f(int j,int i){
	return -2*a*sm[j]*sm[i]+a*sm[j]*sm[j]-b*sm[j]+dp[j];
}