DPまとめコンテスト T - Permutation
問題
<と>のみからなる長さ$ N - 1の文字列$ sが与えられます。$ (1,2,\dots,N)を並べ替えた順列$ (p_1, p2, \dots, p_N)で、$ p_iと$ p_{i+1}の大小関係が$ s_iとなるようなものは何通り作れるでしょうか?
制約
$ 2 \leq N \leq 3000
考察
大小関係のみが問題なので
$ {\rm dp}_{i,j}を$ p\lbrack 0,i \rbrackを考慮して、最後の文字より大きいものが$ j個ある場合の数
とすると、
$ s_iが
<の場合
$ {\rm dp}_{i,j}からは、現在の数より大きな$ j個の数が選べるので$ {\rm dp}_{i+1,j-1}, {\rm dp}_{i+1,j-2}, \dots, {\rm dp}_{i+1,0}に遷移します。
>の場合
$ {\rm dp}_{i,j}からは、現在の数よりも小さなものべます。一番小さくできて、それまでに使った$ i+1個を除いた$ N - 1 - (i+1)個なので$ {\rm dp}_{i+1,j}, {\rm dp}_{i+1,j+1}, \dots, {\rm dp}_{i+1,N-i-2}に遷移します。
これを愚直に実装すると遷移で$ O(N^2)かかってしまいますが、何度も同じ和を計算している部分を累積と差分のみから計算するようにすることで遷移を$ O(N)にすることができます。
全体での時間計算量は$ O(N^2)となります。
code:cpp
int N;
string s;
int main() {
cin >> N >> s;
vector<vector<ModInt>> dp(N, vector<ModInt>(N, 0));
rep(i, N - 1) {
for (int j = N - 2; j >= 0; --j) {
}
} else {
for (int j = 0; j < N - i - 1; ++j) {
}
}
}
return 0;
}
参考