【SPOJ-ALIEN2】Aliens at the train, again!【DP】

제목:
두 개의 기차역 A와 B가 있는데 각각 n개의 플랫폼이 있고 각 플랫폼에는 몇 명의 사람이 있다.외계인은 1번 플랫폼에서 출발한다. (그는 A 또는 B에서 시작할 수 있다.) 매번 그는 현재 기차역을 따라 계속 가거나 다른 기차역으로 전환할 수 있다.i번 플랫폼에서 전환하면 만나는 사람이 Ai+Bi입니다.하지만 외계인이 만나는 사람은 k를 넘으면 안 된다.외계인은 최대 몇 번 플랫폼까지 갈 수 있고, 최소 몇 명을 만날 수 있느냐고 물었다.(다음 단계에서 총 인원이 k보다 많으면 외계인은 현재 플랫폼에서 내린다.)
비교적 간단한 dp.

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 10005, inf = 0x3f3f3f3f;

int n, k, a[maxn], b[maxn], dp[maxn][2];

inline int iread() {
	int f = 1, x = 0; char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) f = ch == '-' ? -1 : 1;
	for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	return f * x;
}

int main() {
	n = iread(); k = iread();
	for(int i = 1; i <= n; i++) a[i] = iread();
	for(int i = 1; i <= n; i++) b[i] = iread();

	dp[1][0] = a[1]; dp[1][1] = b[1];
	for(int i = 2; i <= n; i++) {
		dp[i][0] = dp[i - 1][0] + a[i]; dp[i][1] = dp[i - 1][1] + b[i];
		dp[i][0] = min(dp[i][0], dp[i][1] + a[i]);
		dp[i][1] = min(dp[i][1], dp[i][0] + b[i]);
		if(dp[i][0] > k && dp[i][1] > k) {
			printf("%d %d
", i - 1, min(dp[i][0] - a[i], dp[i][1] - b[i]));
			return 0;
		}
	}

	printf("%d %d
", n, min(dp[n][0], dp[n][1]));
	return 0;
}