Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2370-62bba959
この記事にトラックバックする(FC2ブログユーザー)

UVa 12524 - Arranging Heaps (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12524

問題概要

一次元世界.石の山がN個 (1000以下) ある.
各場所はX[i]で,そこの石の重さはW[i].(X[i]は単調増加)
石のある場所の数をK個にしたい.各場所はもともと石があった場所と一致させなければならない.
石はX軸の正方向にのみ移動可能で,移動距離×重さがコストとしてかかる.
最小コストを求める問題.

解法

ナイーブなDPだとO(N^2 K)かかってしまうが,適当に枝刈りして高速化したら通った.
想定解法はおそらくMonge性か何かを使ってO(N^2)にするのだと思う.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2370-62bba959
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。