問題
n要素の数列c[]とl[]が与えられる.
l[]の中からいくつか一つずつ選び,これらが互いに素となるような条件化でcの総和を最小にする問題。
解法
dp.
A(t) : lからいくつかとってgcdしてtにした時の最小コスト.
とおいて更新。
0<= t <= 10^9なのでmapでやる。
理論計算機科学 (Thoerotical Computer Science) の色んな定理やアルゴリズムを紹介していきます. 基本的には日本語の資料がほとんどないような知見を解説していきます. 執筆者: 清水 伸高 https://sites.google.com/view/nobutaka-shimizu/home
概要 加法的組合せ論における基本的な定理の一つとして, Changの不等式と呼ばれるものがあります. これは, ベクトル空間 $\mathbb{F}_2^n$ の部分集合 $A\subseteq \mathbb{F}_2^n$ に対し, その指示関数の各フーリエ係数を見たとき, ...
0 件のコメント:
コメントを投稿