2014-12-25から1日間の記事一覧

Codeforces Round #284 B Name That Tune

問題概要 N種類の曲があり、それらを順番に流す。聞いている側が曲名が分かり次第流す側に伝える。 流す側は伝えられたらすぐに次の曲を流す。 各曲には認知度p[i]があり毎秒ごとにp[i]%の確率で、そこから1秒で曲名がわかる。 また、各曲の歌詞には曲名がは…

PKU 3612 Telephone Wire

PKU

クリスマスですね。日本語の解説記事がなかったので。 まずは普通に dp[i][j]:=i番目のポールを高さjにする時のそこまでのペナルティの合計の最小値 (不可能なときはINF)として漸化式をたててみると dp[i][j] = min{dp[i-1][k]+abs(k-j)*C | 0 となりますが…