Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Aizu 1204 - Pipeline Scheduling (この記事を編集する[管理者用])

Source

ACM/ICPC Tokyo 1998
UVa 690
ZJU 1661
Aizu 1204

問題概要

5*nの一部分黒い,一部分白いピースが与えられる.
白い部分は重なってもよく,黒い部分が重なってはいけないという状況で,5*kに10個敷き詰める.
敷き詰められる最小のkを求める問題.
nは20以下.

解法

メモ付探索.状態は敷き詰めなくて残りのピースの数,現在の敷き詰めたパターンの右からn列.
メモリ使用量が見積もれないけれど,ジャッジデータに対する状態数はそんなに多くない様子(高々数万程度のオーダー).
Aizu Online JudgeだとWAで通らないけど,uoa==3の人も同じらしいのでそのうち修正されると信じている.
(追記) Aizuは2009-08-27にジャッジミス修正された.

記事更新履歴 (2009-08-28 01:50)

ソースにZJUへのリンクを追加.
Aizuのジャッジミス修正に関して追記.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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