SRM594Div1Easy
問題
N個の惑星の相対サイズAとM個の惑星の相対サイズBが与えられる。各要素は中心からの距離が近い順に並べられている。相対サイズとはある基準に対して何倍であるかを示す値である。AとBそれぞれの中では基準は同一であるが、AとBで同じ基準であるとは限らない。
この時の最小の惑星の数を求めよ。
解法
最長共通部分列で答えが導ける。
基準を同じにするためにAとBそれぞれから一要素だけ選択し、その要素を選択していない方のすべての要素にかける。
計算量
N個の惑星の相対サイズAとM個の惑星の相対サイズBが与えられる。各要素は中心からの距離が近い順に並べられている。相対サイズとはある基準に対して何倍であるかを示す値である。AとBそれぞれの中では基準は同一であるが、AとBで同じ基準であるとは限らない。
この時の最小の惑星の数を求めよ。
最長共通部分列で答えが導ける。
基準を同じにするためにAとBそれぞれから一要素だけ選択し、その要素を選択していない方のすべての要素にかける。