Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SPOJ 5271 - A Coin Game [XOINC] (この記事を編集する[管理者用])

Source

USACO NOV09 Silver Division
SPOJ 5271 [XOINC]

問題概要

数字の書かれたカードがカードが2000枚以下重ねて置いてある.カードに書かれている数字はわかっている.
2人でゲームを行う.順番にカードを上からとっていく.
最初は1枚か,2枚取れる.次は,1枚以上,前相手が取った枚数の2倍以下だけ取れる.
両方最適に動いた場合,先手が獲得できる最高点を求める問題.

解法

dp[残りカード枚数][前相手が何枚取ったか]を記録しながらメモ付探索.
ただし,dp[a][b]を計算するとき,次に取るカードの枚数は2b-1枚と2b枚だけ計算して,それ未満の場合はdp[a][b-1]の結果を使う.
計算時間量,領域量ともにO(n^2).

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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