2015年2月6日金曜日

CF 510 D

問題

n要素の数列c[]とl[]が与えられる.
l[]の中からいくつか一つずつ選び,これらが互いに素となるような条件化でcの総和を最小にする問題。

解法

dp.
A(t) : lからいくつかとってgcdしてtにした時の最小コスト.
とおいて更新。
0<= t <= 10^9なのでmapでやる。

0 件のコメント:

コメントを投稿