Codeforces ECR #094 : E. Clear the Multiset

この回もどうにか全完。
https://codeforces.com/contest/1400/problem/E

問題

N要素の整数列が与えられる。
以下のいずれかの処理を任意の順で行える時、全要素を0にするのにかかる処理回数は何通りか。

• 1つの要素を、負にならない範囲で任意の整数まで減少させる。
• ある区間を、値が負にならない場合に1ずつ減らす

解法

f(L,R,v) := 区間A[L,R)において、すでに区間全体において値を減らす処理がv回行われているとき、その後全要素を0にするまでの最小処理回数
とする。
求めたいのはf(0,N,0)である。

f(L,R,v)の値の最小値は、以下のいずれかである。

• 全要素を前者の処理で空にする場合、R-L回かかる。
• A[L]～A[R-1]の最小値をA[x]とするとき、A[x]=0になるまでは後者の処理を行い、あとは再帰的に[L,x)と[x+1,R)に対して処理を行う。すなわち(A[x]-v)+f(L,x,A[x])+f(x+1,R,A[x])。

int N;
ll A[5050];

ll hoge(int L,int R,ll v) {
	if(L>=R) return 0;
	if(L+1==R) return A[L]>v;
	
	int mi=L;
	int i;
	for(i=L;i<R;i++) if(A[i]<A[mi]) mi=i;
	
	ll ret=min({(ll)R-L,A[mi]-v+hoge(L,mi,A[mi])+hoge(mi+1,R,A[mi])});
	
	return ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	cout<<hoge(0,N,0)<<endl;
}

まとめ

意外にシンプルなコードだった。