yukicoder : No.1378 Flattening

解法はシンプル。
https://yukicoder.me/problems/no/1378

問題

1～NのPermutationである整数列Aが与えられる。
隣接する2要素を、ともに小さい方の値に合わせる、という処理を任意回数行うとき、構成できる数列は何通りか。

解法

f(n,k) := 元々Aのうち先頭のn要素までが、最終的なk要素までを占めるような組み合わせ
とする。f(0,0)=1から初めてf(N,N)を求めて行こう。

A[i]に対し、LをA[L]≦A[i]を保てる最小の値、RをA[R]≦A[i]を保てる最大の値とすると、A[i]はL要素目からR要素目までに配置することができる。
そこでL≦x≦Rに対し、f(i,x) = sum(f(i-1,y)) (y≦x)と計算できる。
よって、累積和を使いながらこの値を更新していこう。

int N;
int A[5050];
ll dp[5050];
const ll mo=998244353;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	dp[0]=1;
	FOR(i,N) {
		x=y=i;
		while(x&&A[x-1]>A[i]) x--;
		while(y<N-1&&A[y+1]>A[i]) y++;
		
		ll S=dp[x];
		for(j=x+1;j<=y+1;j++) {
			(S+=dp[j])%=mo;
			(dp[j]+=S+mo-dp[j])%=mo;
		}
	}
	
	cout<<dp[N]%mo<<endl;
	
}

まとめ

言われてみると簡単なのだけど、さっと思いつかなかった。