競プロはじめました

競プロ初心者のブログ

DP

POJ1065

POJ1065 http://poj.org/problem?id=1065 DP問題の練習です。 ソートして順次大きい方からつなげていけば終わりです。 久しぶりだったのでc++のいろいろな書き方忘れちゃって時間かかりました。 あと、終わってから気づいたのですが、subsetはvectorである必…

POJ1742

POJ1742 1742 -- Coins 今回もDPの練習です。 最初は入れ子ループを何重にも張り巡らしてしまい、タイムアウトしてしまいました。 あとコインが何枚残っているかをメモすれば効率化を計れるんですね。 蟻本で読んだ覚えがあってもいざ自分で実装するとなると…

POJ2385

POJ2385 2385 -- Apple Catching DPの練習問題です 最初問題を読み間違えて、Wを移動してからW分待つと再び移動できるようになると解釈して、一時間くらい悩みました。 英語力の欠如です。 問題の正しい理解ができてからは比較的すぐに実装することができま…