글 읽기 - 14%에서 틀립니다.

lyzqm 6년 전 1

dp로 3가지 경우를 탐색합니다.

현재 학생을 흑으로 할 경우, 현재 학생을 백으로 할 경우, 현재 학생을 그냥 넘기는 경우

어디서 잘못됬을 까요?

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF (987654321)
#define LINF (INF+INF)
int	state[1111][2];
int N;
int dp[1111][15][15][3];
int solve(int here, int cnt1, int cnt2, int flag) {
	if (cnt1 == 15 && cnt2 == 15) return 0;
	if (here == N) return -INF;

	int &ret = dp[here][cnt1][cnt2][flag];
	if (ret != -LINF) return ret;
	ret = max(ret, solve(here + 1, cnt1, cnt2, 2));
	if (cnt1 + 1 <= 15)
		ret = max(ret, solve(here + 1, cnt1 + 1, cnt2, 0) + state[here][0]);
	if (cnt2 + 1 <= 15)
		ret = max(ret, solve(here + 1, cnt1, cnt2 + 1, 1) + state[here][1]);
	return ret;
}
int main() {
	for (int n = 0;n < 1111;n++)for (int m = 0;m < 15;m++)for (int k = 0;k < 15;k++)for (int p = 0;p < 3;p++)
		dp[n][m][k][p] = -LINF;
	while (scanf("%d%d", &state[N][0], &state[N][1]) == 2) { N++; }
	printf("%d\n", solve(0, 0, 0, 0));
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

14%에서 틀립니다.

lyzqm 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말