yukicoder : No.952 危険な火薬庫

区間の二乗和というとね。
https://yukicoder.me/problems/no/952

問題

N個のドアがあり、それぞれ危険度R[i]が設定されている。
連続して開いているドアがあるとき、そのドア群全体の危険度は危険度の総和の二乗とする。
ドアをk個開けた場合のドア群の危険度の総和の最小値を、k=1～Nについて求めよ。

解法

k個開けた場合ではなくm個閉めた場合を考える。
f(n,m) := ドアの先頭n個のうちn個めを閉めており、かつn個めまでに閉めたドアがm個である場合のそこまでの危険度の総和の最小値
とする。
仮に0番と(N+1)番に常にしまったドアがあるとして、f(0,0)=0から初めてf(N+1,m)を求められれば、k個開けた場合の危険度はf(N+1,N+1-m)が解となる。

S(x) := R[1]～R{x]の累積和とする。
n個めの次に占めるドアをn'とすると、f(n',k+1) = min(f(n,k) + (S(n'-1)-s(n))^2)となる。
この式は展開するとS(n'-1)の1次式となるので、convex hull trickで高速に求めることができる。

template<typename V> struct ConvexHull {
	deque<pair<V,V>> Q;
	V calc(pair<V,V> p, V x) {
		return p.first*x+p.second;
	}
	int dodo(pair<V,V> A,pair<V,V> B, pair<V,V> C) { // max or min
		return ((__int128)(A.second-C.second)*(B.first-A.first)<=(__int128)(A.second-B.second)*(C.first-A.first));
	}
	void add(V a, V b) { // add ax+b
		Q.push_back({a,b});
		int v;
		while((v=Q.size())>=3 && dodo(Q[v-3],Q[v-2],Q[v-1]))
			Q[v-2]=Q[v-1], Q.pop_back();
	}
	V query(V x) {
		int L=-1,R=Q.size()-1;
		while(R-L>1) {
			int M=(L+R)/2;
			(((calc(Q[M],x)>=calc(Q[M+1],x)))?L:R)=M;
		}
		return calc(Q[R],x);
	}
};

int N;
int A[3030];
ll S[3030];
ll cost[3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i+1];
		S[i+1]=S[i]+A[i+1];
	}
	
	FOR(x,N+2) FOR(y,N+2) cost[x][y]=1LL<<60;
	cost[0][0]=0;
	for(i=1;i<=N+1;i++) {
		ConvexHull<ll> ch;
		for(x=i;x<=N+1;x++) {
			ch.add(-2*S[x-1],cost[i-1][x-1]+S[x-1]*S[x-1]);
			cost[i][x]=ch.query(S[x-1])+S[x-1]*S[x-1];
		}
	}
	
	for(i=1;i<=N;i++) cout<<cost[N+1-i][N+1]<<endl;
	
	
}

まとめ

★3.5あたりは一番気持ちよく解けるな。