パ研合宿2020 第1日「SpeedRun」 : N - 背の順

こちらは普通に解けた。
https://atcoder.jp/contests/pakencamp-2020-day1/tasks/pakencamp_2020_day1_n

問題

全要素が異なるN要素の整数列Aが与えられる。
ここからいくつか要素を取り除き、Aが昇順となるようにしたい。
ある区間A[L...R]を取り除くのにかかるコストはA[L]+A[R]とする。
Aを昇順にするのにかかる最小コストを求めよ。

解法

f(i) := Aのprefixのうち、A[i]を残し、かつA[i]が最大であるような残し方のうち、最小コスト
とする。
解の候補は以下の通りである。

• i＜N-1ならf(i)+A[i+1]+A[N-1]
• i=N-1ならf(i)

あとはf(i)を求めよう。
A[x]の小さい順にxを処理することを考える。
その時f(x)は以下の最小値のいずれかである。

• x-1番目を残す場合、f(x-1)
• x-1番目より手前のy番目を残す場合、f(y)+A[y+1]+A[x-1]

そこで、f(y)+A[y+1]をSegTreeなどで区間最小値を取れるようにしておけば上記最小値を高速に求められる。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1LL<<60;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]); //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<ll, 1<<20> st;
ll N;
int A[202020];
ll dp[202020];
pair<int,int> P[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i+1];
		P[i]={A[i+1],i+1};
		dp[i+1]=1LL<<30;
	}
	ll ret=A[1]+A[N];
	st.update(0,A[1]);
	sort(P,P+N);
	FOR(i,N) {
		x=P[i].second;
		dp[x]=dp[x-1];
		if(x>=2) dp[x]=min(dp[x],st.getval(0,x-1)+A[x-1]);
		
		if(x<N) {
			ret=min(ret,dp[x]+A[x+1]+A[N]);
			st.update(x,dp[x]+A[x+1]);
		}
		else {
			ret=min(ret,dp[x]);
		}
	}
	cout<<ret<<endl;
	
	
	
}

まとめ

若干面倒だけどね。