TopCoder SRM 565 Div1 Easy MonstersValley

さてSRM565。
Easyはすんなり解けた。Mediumは方針自体はあっていたけど、最後までバグが取りきれずsubmitできなかった。
最近レートがグダグダなので、Easyだけでもなんとかレートは上がったけどね。

この問題はDiv2 Mediumを少し簡単にしたもの。
http://community.topcoder.com/stat?c=problem_statement&pm=12350

モンスターをお金を払って仲間にし、他のモンスターを倒していく。
全モンスターを倒すのに必要な最小なお金を答える問題。

モンスターの強さは10^12と最大値が大きいが、お金が上限2、モンスター数が上限50なので、お金に応じてDPすればよい。
お金ごとに、その時点の（最大の仲間にしたモンスターの強さの合計）を持っておく。

class MonstersValley {
	public:
	int minimumPrice(vector<long long> dread, vector <int> price) {
		ll dp[2][200];
		int N=price.size();
		
		int i,j,k,cu,ne;
		FOR(i,2) FOR(j,200) dp[i][j]=-1;
		
		dp[0][0]=0;
		FOR(i,N) {
			cu=i%2;
			ne=1-cu;
			FOR(j,200) dp[ne][j]=-1;
			
			FOR(j,200) {
				if(dp[cu][j]>=0) {
					if(dp[cu][j]>=dread[i])
						dp[ne][j]=max(dp[ne][j],dp[cu][j]);
					dp[ne][j+price[i]] = max(dp[ne][j+price[i]],dp[cu][j]+dread[i]);
				}
			}
		}
		
		int mi=999;
		ne=N%2;
		for(j=199;j>=0;j--) if(dp[ne][j]>=0) mi=j;
		return mi;
	}
};

まとめ

Easy250ptでいきなりDPは珍しいかな？
強さでなくお金でDPするのがちょっと珍しい。