Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11826 - Shuffle (この記事を編集する[管理者用])

Source

One more National Programming Contest 2010 (2010-09-04)
UVa 11826
SPOJ 7333 [SHUFFLEN] (問題名: Shuffle Music) (2010-09-20 11:40追加)

問題概要

ある音楽プレイヤーでN曲の曲をランダム再生モードで聞くとき,全部の曲が流れるまでの平均日数を求める問題.
流れる曲は,電源をつけてから流れていない曲の中から選ばれ,過去再生した曲は選ばれる確率が他の曲と比べて2倍である.
電源を切っても過去再生した曲リストはリセットされない.
朝と夜の通勤時間に曲を聞き,朝,夜の通勤が終わるたびに電源を切る.
朝に聞ける曲の数の範囲と,夜に聞ける曲の数の範囲が与えられる.実際に聞ける曲の数はその範囲で一様分布に従う.
Nは75以下,朝・夜に聞ける曲の範囲は30曲以下.

解法

ループのあるDP.
 dp[残り曲数][今は朝か夜か]
として,
 X = dp[k][朝], Y = dp[k][夜]
のとき
 X = a Y + c
 Y = b X + d
という形になるので,これを解いてループを解決してあげる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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