地下都市シオン

「アルゴリズムデザイン」にのっている演習問題。
ストーリーが、某主人公が救世主になってマシンと戦争する映画にとてもにている。がその辺は省略。
問題
n秒間に渡りロボットがくる。i秒目にはXi台のロボットがくることが分かっている。
ロボットを倒すためにEMP(電磁気パルス)を使用する。EMPは最後に使ってからj秒経過していればFj台のロボットを倒すことができる。
つまりEMPをi秒目にj秒の充電で使用した場合、倒せるロボットはmin(Xi, Fj)台。
適切にEMPを使用した場合、倒せる敵の最大数を求めるプログラムを作れ。

解法
動的計画法を使う。
i秒目までで倒せる最大の敵の数を順に求めていく。
詳しくはコード中のコメントを参照。
たぶん、これで大丈夫だと思う。

実装

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

const int MAX_N = 1000; //最長の時間
int N;
int robot[MAX_N + 1]; //敵
int zyuden[MAX_N + 1]; //充電関数
int dp[MAX_N + 1];
/*
dp[i] = i秒までに倒せる最大のてきの数
dp[0] = 0;
dp[i] = max(dp[i - j] + min(zyuden[j], robot[i])) (j >= i)
*/
int solve(){
	dp[0] = 0;
	for(int i = 1; i <= N; i++){
		dp[i] = 0;
		for(int j = 1; j <= i; j++){
			dp[i] = max(dp[i], dp[i-j] + min(zyuden[j], robot[i]));
		}
	}
	return dp[N];
}

int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; i++)
		scanf("%d", &robot[i+1]);
	for(int i = 0; i < N; i++)
		scanf("%d", &zyuden[i+1]);
	printf("%d\n", solve());
	return 0;
}