AtCoder ABC #209 : F - Deforestation

典型だったのに別アプローチ行ってしまい、遅刻も相まって時間内に間に合わず。
https://atcoder.jp/contests/abc209/tasks/abc209_f

問題

N要素の整数列Hが与えられる。
要素iを選択すると、コストをH[i-1]+H[i]+H[i+1]払い、H[i]=0にできる。
Hをすべて0にする総コストが最小となる、iの選択順は何通りか。

解法

まずコストが最小となる条件を考える。
iとi+1どちらを先に選択するのが良いか。

• iを先に選択すると、コストはH[i-1]+H[i]+2*H[i+1]+H[i+2]
• i+1を先に選択すると、コストはH[i-1]+2*H[i]+H[i+1]+H[i+2]

ということで、値が大きい方を先に選択した方が良いことがわかる。

あとはそれを満たすiの並び順を考えよう。
f(n,k) := Hのprefix n要素に対し、条件を満たす並べ方のうち、末尾の要素がk番目にくるものの組み合わせ数

n+1番目の要素をどこに入れるかを考える。

• H[n]=H[n+1]なら、両者の順は問わないのでf(n+1,k) = sum(f(n,*))
• H[n]＜H[n+1]なら、n+1番目の要素はn番目より前に選択しないといけないので、f(n+1,k) = f(n,k)+f(n,k+1)+...
• H[n]＞H[n+1]なら、n+1番目の要素はn番目より後に選択しないといけないので、f(n+1,k) = f(n,0)+f(n,1)+...+f(n,k-1)

f(n,*)の累積和を適宜取っていくと、O(N^2)で計算できる。

int N;
ll H[4040];
const ll mo=1000000007;

ll dp[4040][4040];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N) cin>>H[i];
	dp[0][0]=1;
	for(i=1;i<N;i++) {
		for(j=1;j<=i;j++) (dp[i-1][j]+=dp[i-1][j-1])%=mo;
		FOR(j,i+1) {
			if(H[i]==H[i-1]) dp[i][j]=dp[i-1][i];
			if(H[i]<H[i-1]) dp[i][j]=(mo+dp[i-1][i]-(j?dp[i-1][j-1]:0))%mo;
			if(H[i]>H[i-1]) dp[i][j]=(j?dp[i-1][j-1]:0);
		}
	}
	
	ll ret=0;
	FOR(i,N) ret+=dp[N-1][i];
	
	cout<<ret%mo<<endl;
}

まとめ

直感的には端から切り倒す方がコスト低そうだけどね。