hotpepsiの練習帳

SRM 647

00:51

Div1 Easy (250) BuildingTowersEasy

問題

• N個の建物を建てる
• 位置x[i]にある建物の高さはt[i]以下であること
• 1番目の建物の高さは0であること
• 隣り合う建物の高さの差は1以下であること
• 建物の高さの最大値を求める

方針

• それぞれのt[i]について、位置yの最大値はt[i]+|x[i]-y|
• それを制約条件として全部の位置の最大値を求める
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_647/BuildingTowersEasy.cpp

• 結果

o-- 161.34pts 219th/511 1410 -> 1460 (+50)

ぎざぎざの山頂のイメージ。

http://togetter.com/li/774013