mmxsrup https://blog.hatena.ne.jp/mmxsrup/ srupのメモ帳 https://mmxsrup.hatenablog.com/ yukicoder dp 組み合わせ 数え上げ 問題 問題概要 組み合わせの数え上げ 解法 まず、すべてソートしてく。全探索をして、それぞれの家族がどのマットを使うかを決める。それが条件を満たしたものであれば、ほかのものは選ぶ選ばないの選択がある。 dpのほうがわかりやすいな。状態数は2つで、1つは、何枚目までを考えているか、もう一つは、条件を満たしている数である。 dp[i][j] := i番目のマットまでで考えて、j=1ならBのマットは条件を満たし、j=2ならBCのマットは条件を満たし、j=3ならすべてのマットの条件を満たすとしてやる。 漸化式は、i番目のマットが、新たに次の条件を満たす大きさであるなら(j=1なら次はc以上の大きさであ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmmxsrup.hatenablog.com%2Fentry%2F2016%2F09%2F30%2F143101" title="yukicoder No.412 花火大会 - srupのメモ帳" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-09-30 14:31:01 rich https://mmxsrup.hatenablog.com/entry/2016/09/30/143101 1.0 100%