読者です 読者をやめる 読者になる 読者になる

AOJ2439 Hakone

AOJ

箱根駅伝。問題概要は略。
解法が面白かったのでメモ

dp[i][j] : 現在i位まで見てj個unmatchedな場合の数
として、
i番目が-ならそのまま,
Dならi番目をそれまでの空いているところに入れるのでj通り,
またi番目にそれまでのを入れる.... dp[i+1][j-1] += dp[i][j] * j * j
スルー.... dp[i+1][j] += dp[i][j] * j

Uなら
i番目にそれまでのを入れる... dp[i+1][j] += dp[i][j] * j
スルー... dp[i+1][j+1] += dp[i][j]

として更新するとO(n^2)で解ける

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n)  for(int i = 0; i < (int)n; ++i)

const int MOD = 1000000007;

int n;
int dp[210][210];

inline void md(int &x, int y){ x += y; if(x >= MOD) x -= MOD; }

int main(){
    dp[0][0] = 1;
    scanf("%d", &n);
    rep(i, n){
	char c[3]; scanf("%s", c);
	if(c[0] == '-') for(int j = 0; j <= i + 1; ++j) dp[i+1][j] = dp[i][j];
	else if(c[0] == 'D'){
	    for(int j = 1; j <= i + 1; ++j){
		md(dp[i+1][j-1], (ll)dp[i][j] * j * j % MOD);
		md(dp[i+1][j], (ll)dp[i][j] * j % MOD);
	    }
	}else{
	    for(int j = 0; j <= i; ++j){
		md(dp[i+1][j], (ll)dp[i][j] * j % MOD);
		md(dp[i+1][j+1], dp[i][j]);
	    }
	}
    }
    printf("%d\n", dp[n][0]);
    return 0;
}