Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

PKU 3769 - Baseball on the Mercury (この記事を編集する[管理者用])

Source

PKU Campus 2010 (POJ Monthly Contest 2010.05.09) (参加記録)
PKU 3769

問題概要

野球っぽいことを行う.
N人の人が順番にバッティングする.
3塁に人がいるなら,犠牲フライっぽいものを,そうでないなら普通にバッティングする.
犠牲フライは成功したら,自分はアウトになり,塁に出てる人たちは,0~2だけ先に進める.
普通のバッティングは失敗したら自分はアウトになり,塁に出てる人たちはそのまま.
成功したら,その成功度合いに対して,バッターと塁に出てる人たちは0~Gだけ先に進める.G=1,2,3,4で成功度合いによって決まる.
同じ塁に1人以上入れない,ホームベースに留まることはできない.
点数計算は,ホームベースに戻ってきた人 - アウトになった人,で計算する.
各選手のバッティングの成功率が与えられたとき,どれだけ進むかを自由に選べるとして,得られる得点の期待値の最大値を求める問題.
Nは10000以下.

解法

DP.
状態は,今何人目のバッターか,1塁に人はいるか,2塁に人はいるか,3塁に人はいるか,で10000*2*2*2状態ぐらい.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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