TopCoder SRM 605 Div1 Hard AlienAndPermutation

TopCoder 動的計画法 確率・場合の数

問題

長さnの順列Pが与えられる。（整数1〜nの順番を並べ替えたもの）


これに対して、次のような操作を高々K回行うことができる。
二つの数(i, j)を選ぶ。i≦k≦jなる全てのkについて、P[k]をmax{P[k]|i≦k≦j}で置き換える。


P = {1, 7, 2, 3, 6, 4, 5}
に対して(2, 4)で操作を行うとP = {1, 7, 7, 7, 6, 4, 5}に変化する。


このような操作の後に出来る数列は何通りあるか、mod 10^9 + 7で求めよ。

制約条件

n≦200
K≦200

方針

なんかO(n^4)の嘘解法を試しに投げてみたら通ってわらった。
操作後の数列をSとする。


dp[i][j][k][l]を、Sがi番目の要素まで完成していて、i番目にはP[j]が来ていて、
残りの操作回数がk回で、lは、P[j]を次も使った場合、コストがかかるかかからないか。


で、状態の遷移は、i + 1番目にどのP[m]を使うか。
mはどこからなら持ってこられるかと言うと、j≦mかつ、mからi+1に持ってきたときに、自分より大きい数を超えていないような場所。


iをjまで動かしたときに自分より大きい数を超えていないかは前計算で計算しておくことができる。
それで、遷移のときにコストのつじつまを合わせて数え上げればO(n^4).


嘘解法通したあとちゃんとeditorialも見た...
想定解は、この遷移を1回だけで済ますというもの。
dp[i][j][k][l]を、Pをi番目の要素まで使っていて、Sをj要素完成させて、残りコストがkで、P[i]をS[j]に持ってくるときにコストを払っていたらl = 1.


これを更新するのだが、
よく考えると、P[i]をS[j]に持ってこられ、かつP[i]をS[j+1]にも持ってこられるなら、必ずP[i]をS[j+1]にも延ばせるので、
iを使わないという選択肢を入れれば、
遷移でS[j]を右に延ばすか延ばさないかだけ考えればよかった。


コストは、P[i]をS[i]にもってくる場合は0.
そうでない場合で、既にコストを払っていたら0, 払っていなかったら1.

ソースコード

O(n^3)
const int mod = (int)1e9 + 7;
int n, dp[201][201][201][2];
bool can[201][201];

int rec(int i, int j, int k, int f){
	//Pのi番目の数字を使っている
	//Sはj番目まで完成した
	//fは伸ばすコストを払ったか
	
	if(k < 0) return 0;
	if(j == n) return 1;
	if(i == n) return 0;
	
	int &res = dp[i][j][k][f];
	if(res >= 0) return res;
	
	res = rec(i + 1, j, k, 0); //skip
	if(can[i][j]) res += rec(i, j + 1, k - (i != j && !f), f || (i != j));
	return res %= mod;
}

class AlienAndPermutation {
	public:
	int getNumber(vector <int> P, int K) {
		
		memset(dp, -1, sizeof(dp));
		memset(can, 0, sizeof(can));
		
		n = P.size();
		
		rep(i, n) rep(j, n){
			if(P[i] < P[j]) continue;
			for(int k = min(i, j); k < max(i, j); k++){
				if(P[k] > P[i]) goto FAIL;
			}
			can[i][j] = 1;
			FAIL:;
		}
		
		return rec(0, 0, K, 0);
	}
};

O(n^4)

700msかからずに通る...実際にいたれる状態数はあまり多くないのかも。

const int mod = (int)1e9 + 7;
int n, dp[201][201][201][2];
bool can[201][201];
class AlienAndPermutation {
	public:
	int getNumber(vector <int> P, int K) {
		
		memset(dp, 0, sizeof(dp));
		memset(can, 0, sizeof(can));
		
		P.insert(P.begin(), 0);
		n = P.size();
		
		rep(i, n) rep(j, n){
			if(P[i] < P[j]) continue;
			for(int k = min(i, j); k < max(i, j); k++){
				if(P[k] > P[i]) goto FAIL;
			}
			can[i][j] = 1;
			FAIL:;
		}
		
		dp[0][0][K][1] = 1;
		
		rep(i, n - 1) rep(j, n) rep(k, K + 1) rep(l, 2) if(dp[i][j][k][l]){
			
			for(int m = j; m < n; m++) if(can[m][i + 1]){
				
				int nk = k - (j == m && l || j != m && m != i + 1);
				if(nk < 0) continue;
				
				int nl = m == i + 1 && j != i + 1;
				(dp[i+1][m][nk][nl] += dp[i][j][k][l]) %= mod;
			}
		}
		int ans = 0;
		rep(i, n) rep(j, K + 1) rep(k, 2) (ans += dp[n-1][i][j][k]) %= mod;
		return ans;
	}
};