問題
https://community.topcoder.com/stat?c=problem_statement&pm=14304
1～Nの数が1つずつある順列を考える。
その順列に対して、「lo-hi-lo triple（以下LHL）」の個数を数える。
lo-hi-lo triple（LHL）
順列Pの i < j < k に対して P[i] < P[j] > P[k] である3つの組
例) 1 3 4 2 1 * 4 2 * 3 4 2 1 3 * 2
というLHLがあるので、個数は3つ
1～Nの数が1つずつある順列は全部でN!個あるが、その中でLHLの個数がK個である数列の個数を数えよ
1 <= N <= 50
0 <= K <= 5000
考察
1. まず、数学的に解けないか考えてみる
2. うーむ。無理そう。組合せといえばDPかな？
3. DPでいけないかな…
4. Nの制限が小さいけど、区間DPとか最大最小を添え字にするとかかな…
5. どれも無理そうだったので、実験して考えてみる
頑張って実験してみる
6. DPで大切なのは「状態をまとめること」
7. 数と場所を決定していくのをうまい具合に調整すると、状態がまとめられて嬉しい
8. この方針で実験して、考えて…
9. 数の小さい順から決定していくと、挿入した所の左側は必ず小さく、右側も必ず小さくなる
1,2,3,4を挿入しながら順列を決定していくとする。 1 ↓ + 2 1 2, 2 1 この2つはどこに3を入れても、増えるLHLの数は変わらないから同一視できる！！ ↓ + 3 3 1 2, 1 3 2, 1 2 3, 3 2 1, 2 3 1, 2 1 3 これらもどこに3を入れても、増えるLHLの数は変わらないから同一視できる！！ だが、増えるLHLの数は変わらないが、「今までのLHLの数は違う場合がある」ので別の場合として分ける
10. dp[何番目の数まで決定して][LHLの数が現時点で何個で] = 場合の数
を更新していけば解ける
実装
typedef long long ll; #define MOD 1000000007 ll dp[55][10050]; class UpDownNess { public: int count(int N, int K) { dp[0][0] = 1; rep(i, 1, N+1) rep(j, 0, K + 1) { rep(k, 0, i) { int left = k; int right = i - 1 - left; dp[i][j + left * right] += dp[i - 1][j]; dp[i][j + left * right] %= MOD; } } return dp[N][K] % MOD; } };
