区間の二乗和というとね。
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あたりは一番気持ちよく解けるな。