ホームページ > 記事 > ウェブフロントエンド > Codeforces ラウンド #214 (ディビジョン 2)??Dima と Salad_html/css_WEB-ITnose
Codeforces ラウンド #214 (ディビジョン 2)??Dima と Salad_html/css_WEB-ITnose
- WBOYオリジナル
- 2016-06-24 12:04:331084ブラウズ
質問リンク
1行a[i]、1行b[i]、aとbは1対1に対応します。 sigma(a)/sigma(b) が k に等しくなるように任意の数値のペアを選択し、このときの sigma(a) の最大値を求めます
この質問の鍵は sigma(a)/sigma( b)== k 処理。この式では、明らかに各数値の比率を使用することはできません。これは累積できず、double 型であるため、DP にすることはできません。各数値がこの式に及ぼす影響を考えてください。 a = k * b である場合、それは明らかに可能です。a が k * b より小さい場合、全体として、より少ない現在の数値ペアで数値を補うためにいくつかの数値ペアが必要になります。つまり、x = を覚えておいてください。 k * b - a、選択されたすべての数値ペアの x の合計はゼロになるはずです。
次に、各数値のペアは実際には正または負の数になります。和がゼロになるいくつかの数値のシグマ (b) の最大値を求め、正と負を分離し、バックパックを使用してそれを解きます
れーい
声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。