Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 4684 - Love for Pizza (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Amritapuri (India) - 2009/2010
LiveArchive 4684

問題概要

ピザの上にトッピングが100000個以下載っている.
各トッピングに点数がつけてあり,ピザを切って,一切れに載っている(自分がとる)点数の和の最大値を求める問題.
点数が負もありうる.
切り方は,中央から2回外に向けて切って,扇形のピースを作る.

解法

arctanの値でソートしたら,後は,連続する部分の和の最大値を求めれば良い.
ループの解消が問題だけど,例えば,始点を1つに決めると,その始点は,自分の取るピースととらないピースのどちらかは跨がないので,最大値と最小値を求めて,最小値の方が自分の取らないピースとする,で良い方など.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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