SRM 366 DIV1 Easy/DIV2 Medium

ChangingSounds
URL: http://community.topcoder.com/stat?c=problem_statement&pm=7973

時刻付きで考えたことのログを取ってみた。

ギタープレイヤー、コンサートを開く　10:47 2011/08/23
全ての曲を同じ音量で弾くのは嫌だ　10:47 2011/08/23
曲ごとにボリュームを変更することにした　10:48 2011/08/23
各曲ごとに音量を上げるか下げるかする　10:49 2011/08/23
1つずつじゃなく、インターバルの量だけ増減する　10:51 2011/08/23

与えられるもの
　ギターの初期音量　10:49 2011/08/23
　ギターの最大音量　10:49 2011/08/23
　0<=音量<=最大音量 10:50 2011/08/23

求めるもの
　音量の最大値 10:50 2011/08/23
　音量が範囲外にならざるを得ないなら -1 10:53 2011/08/23

　→貪欲にやれるか？　10:52 2011/08/23
　　←出来るだけ増やす　10:54 2011/08/23
　　　←下げざるを得ないときだけ減らす　10:54 2011/08/23
　→全探索で間に合うか？　10:54 2011/08/23
　　←changeIntervalsの要素数は最大50個 10:55 2011/08/23
　　←音量の最大値は最大で1000 10:55 2011/08/23
　　　→DPのにおいがする　10:55 2011/08/23
　　　　←[何番目まで使ったか][音量]　10:56 2011/08/23
　→動的計画法　10:57 2011/08/23
　　←dp[i][j]: i番目のギターを演奏したとき音量jが最大値かどうか　10:58 2011/08/23
　　　←dp[0][beginLevel] = true 11:01 2011/08/23
　　　　←dp[i][j]がtrueならdp[i+1][j+I[i] ], dp[i+1][j-I[j] ]もtrueになるはず 11:02 2011/08/23
　→とりあえず動的計画法でやってみる　11:03 2011/08/23
　　→サンプル通った　11:12 2011/08/23　終了