Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12432 - Inked Carpets (この記事を編集する[管理者用])

Source

BUET Inter-University Programming Contest - 2011 (2012-02-18)
UVa 12432

問題概要

長さL (10^9以下) の床があり,カーペットを重なりなく敷き詰める最小コストと,その最小コストを達成するような色の変化の最小数を求める問題.
色はM (50以下) 種類あり,それぞれのペンキの値段が与えられる.
また,既存のカーペットはN (1000以下) 種類あり,それぞれの情報は
 区間[st, ed]を覆うことができる (区間[st+1, ed+1]などには使えないし,一部分だけ使うこともできない)
 色
 価格
 値引き率(後述)
が与えられる.
敷き詰めるときは,必ず,区間の最初から敷き詰めなければいけない.
できることは,あるカーペットを買ってそのまま敷くか,長さ1の無色カーペット(無料)をインクで塗って敷くかのどちらか.
カーペットを買うとき,同じ色のカーペットを3回以上連続で買うと,3回目以降はmax(価格 - 値引き率, 0)だけの価格で買うことができる.
途中で無色カーペットを使うと,連続して買っていることにならない.

解法

最後に買ったカーペットと,同じ色のカーペットを連続で買ったかどうかを状態としてDPする.
無色カーペットを使うときは,左右と同じ色か,最もインクの易い色しか考えなくて良い.(Mは微妙に小さいので全部考慮しても通る?)

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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