CODE FESTIVAL 2015 決勝 G. スタンプラリー
解法
preorderがCになり、かつ子に関してi < jが成り立つならC[i] < C[j]が成り立つような木を数え上げればいい。
C = [1,3,2,5,6,9]ならこんな感じの木。
こんなのはダメ。preorderは合ってるけど、3より先に2に降りてしまう。
f(L,R)=(Lを根とし、C[L..R-1]を使って作ることのできる木の総数)とすればメモ化再帰で解ける。Lは複数の部分木を持つかもしれない。もし3個以上部分木があるのであれば、仮想的にm-1を根とした1個の部分木にまとめてあげると良い。こうするとLの部分木の数は高々2個と考えることができる。
漸化式はf(L,R)=f(L+1,R)+Σf(L+1,m)*f(m-1,R)、ただしmはC[L+1] < C[m]。
#include <bits/stdc++.h> #define GET_MACRO(a, b, c, NAME, ...) NAME #define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__) #define rep2(i, a) rep3 (i, 0, a) #define rep3(i, a, b) for (int i = (a); i < (b); i++) #define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__) #define repr2(i, a) repr3 (i, 0, a) #define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define chmin(a, b) ((b) < a && (a = (b), true)) #define chmax(a, b) (a < (b) && (a = (b), true)) using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll dp[300][300]; ll c[1010]; ll f(int l, int r) { if (r - l <= 1) return 1; if (dp[l][r] > 0) return dp[l][r]; ll res = f(l + 1, r); rep (m, l + 1, r) if (c[l + 1] < c[m]) { res += f(l + 1, m) * f(m - 1, r); res %= mod; } return dp[l][r] = res; } int main() { int n; cin >> n; rep (i, n) { cin >> c[i]; c[i]--; } if (c[0] != 0) { cout << 0 << endl; return 0; } cout << f(0, n) << endl; return 0; }
コメント
かなり混乱してたけど何とか解けてよかった。