AOJ 2439 Hakone

AOJ 競技プログラミング

いっぱい☆ついていたけれど。

問題

Hakone | Aizu Online Judge

感想

DPですね。今回は少しわかり辛いのですが。

まず考えることなのですが、前の中継所でのその順位にはいる候補は。

  • 現在その順位より上にいて’U'である。
  • 現在その順位より下にいて'D'である。
  • 現在もその順位にいて'-'である。

の三通りであるということ。

上から順番に求めていきたいことを考えていくといい感じになりそうです。今回は、

dp[i][j][k] := i番目まで見た、前回の中継所での順位について、見た順位の中でjチーム分未確定のままにしているところがあり、kチームの未確定な'U'のチームがあるときの組み合わせ。

という、少々特殊な状態を持ちました。

となると、上から見ていったときに、

  • そこが'U'ならば、そのチームを前の中継所でどこにいたかを保留した後、その場所に未確定にしていたほかの'U'のチームを入れるかどうか。
  • そこが'D'ならば、そのチームを未確定にしたj個のうちのどこかに入れた後、その場所に未確定にしていたほかの'U'のチームを入れるかどうか。
  • そこが'-'ならばそのまま。

という遷移が考えられます。

UD二つを同時に管理するのはむつかしいので、片方はすぐに決めてしまおうって感じですね。

上手いこと状態がまとめられるかが肝ですね～

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef DEBUG_MODE
    #define DBG(n) n;
#else
    #define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define MOD 1000000007
 
typedef long long ll;
typedef pair<ll,ll> P;
 
ll dp[222][222][222];
 
int main(){
     
    int n;cin >> n;
    vector<char> v(n);
    REP(i,n)cin >> v[i];
     
    dp[0][0][0] = 1;
     
    REP(i,n){
        REP(j,n){
            REP(k,n){
                if(dp[i][j][k]){
                    DBG(cout << "ijk ; " << i << ' ' << j << ' ' << k  << ' ' << dp[i][j][k] << endl;)
                    if(v[i] == '-'){
                        dp[i+1][j][k] += dp[i][j][k];
                        dp[i+1][j][k] %= MOD;
                    }
                    else if(v[i] == 'U'){
                        if(k > 0){
                            dp[i+1][j][k] += dp[i][j][k] * k;
                            dp[i+1][j][k] %= MOD;
                        }
                        dp[i+1][j+1][k+1] += dp[i][j][k];
                        dp[i+1][j+1][k+1] %= MOD;
                    }
                    else{
                        if(j > 0){
                            dp[i+1][j][k] += dp[i][j][k] * j;
                            dp[i+1][j][k] %= MOD;
                            if(k > 0){
                                dp[i+1][j-1][k-1] += dp[i][j][k] * j * k;
                                dp[i+1][j-1][k-1] %= MOD;
                            }
                        }
                    }
                }
            }
        }
    }
     
    cout << dp[n][0][0] << endl;
     
    return 0;
}