ferinの競プロ帳

競プロについてのメモ

2017-09-11から1日間の記事一覧

AOJ0562 JOI国のお買い物事情

問題ページ JOI 国の買い物事情 | Aizu Online Judge 解法 最短経路問題で始点が複数あるパターンなので始点をまとめる架空の頂点をつくってやればdijkstra一回で各頂点への最短距離がわかる。各頂点への最短距離がわかっていれば各辺のどの位置が最短距離が…

AOJ0550 お菓子の分割

問題ページ お菓子の分割 | Aizu Online Judge 解法 いかにもDPの雰囲気があるのでDPを考える。AくんとBくんでお菓子を分け合うとして dp[k][i][j] = (k番目まででAくんがi個取って最後に取ったのがAくんならj=0、Bくんならj=1) とおいてDPをする。遷移に必…