TopCoder SRM605
なんで DP 2 個なんだろう
250
ハンバーガーがたくさんあり，それぞれ type と taste が決まっている．
このうちの 0 個以上を食べる．このときのうれしさは，(type の種類数) * (taste の和) である．最大値を求めよ．
type ごとに，使った時の得られる taste の最大値を求めて，それをソートして種類数を全部試す．
450
1〜2N の数を 2 つの N 個ずつの集合 A, B に分ける．A の i 番目に小さい数と，B の i 番目に小さい数の差は K 以上でないといけない．分け方は何通りか．
dp[A に入れたものの数][B に入れたものの数][最近 K-1 個の様子] として，1 から順に入れる DP．
A と B に今まで同じだけ入れたときは，次の数はどちらでも自由に入れることができる．
A のほうが多いときは，A に入れるのはかまわないが，B に入れるためには対応する A が十分前に入れたものでないといけない．それは最近 K-1 個の様子を見ればわかる．B のほうが多い時も同様．
1000
1〜N の並び替えの列に対して，「ある範囲の数をすべて，その範囲の最大値で置き換える」ことが K 回までできる．何通りの列が考えられる？
最初に a が b より前に出てくるときに，後で a が b より後ろに出てくることはありえない．
また，ある数を最初の位置から，自分より大きい数をまたいだところに置くような操作は存在しない．
一方，最大値が小さいものから順に操作を行うことにすると，列が上の数の置ける範囲の制約と登場する数の順序の制約の両方を満たしてさえいれば，何回かの操作でその列に変えることができる．
操作の回数を消費しないのは，「最終的に列に登場しない」もしくは「最終的な列に登場するが，最初からあった位置のみである」ときである．
これは dp[位置][次に使おうとしている数][操作した数][もう操作数を数えたか] で DP すると求められる．
