SRM 366 250pt: ChangingSounds

TopCoder

問題概要

数列A(長さN(<50))が与えられる。今メモリに非負の初期値が設定されている。メモリにA[i]の値を順に加えるか引くかする。メモリの値は常に[0,V](V<1000)の範囲に収めなければならない。最終的にメモリの値をどれだけ大きくすることができる。

考えたこと

  • 非常によくあるDPっぽい。
  • でもeasyでDPって珍しい気もするし、何か他の解法もあるのかな？
  • ちょっと考えたけど、DPで簡単にかけるからもういいや。
  • 今回は配るDPが一番しっくりくる。
  • 書いた。最後のサンプル合わない。
  • 配列のインデックス間違えてた。直したら無事通った。

practiceで通ったコード

#include <vector>
#include <algorithm>
using namespace std;

const int MAX_V = 1009;
const int MAX_N = 59;

bool dp[MAX_N][MAX_V];

struct ChangingSounds {

	int maxFinal(vector <int> changeIntervals, int beginLevel, int maxLevel) {
		const int N = changeIntervals.size();

		//DPテーブルの初期化
		dp[0][beginLevel] = true;

		//DP
		for(int i=0; i<N; i++){
			for(int vol = 0; vol <= maxLevel; vol++)if(dp[i][vol]){
				int lower = vol - changeIntervals[i];
				int higher = vol + changeIntervals[i];

				if(lower >= 0) dp[i+1][lower] = true;
				if(higher <= maxLevel) dp[i+1][higher] = true;
			}
		}

		//最大値を探す
		int ret = -1;
		for(int i=0; i<=maxLevel; i++)if(dp[N][i]){
			ret = i;
		}

		return ret;
	}

};