글 읽기 - 간단한 DP인데 어디가 잘못된걸까요?

freewizard 5년 전 0

안녕하세요,

간단하다고 생각하는데 문제되는 부분을 찾지 못해서 질문드립니다.

혹시 잘못된 부분을 찾을 수 있으신가요?

미리 감사드립니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

int n;

int arr[100001][2];
int cache[100001][2];


int solve(int curr, int mode) {
	
	if (curr == n) return 0;
	if (cache[curr][mode] != -1) return cache[curr][mode];

	int ret = 0;
	if (mode == 0) {
		ret = max(ret, solve(curr + 1, 1) + arr[curr][0]);
		ret = max(ret, solve(curr + 1, 2) + arr[curr][1]);
		ret = max(ret, solve(curr + 1, 0));
	}
	else if (mode == 1) {
		ret = max(ret, solve(curr + 1, 2) + arr[curr][1]);
		ret = max(ret, solve(curr + 1, 0));
	}
	else {
		ret = max(ret, solve(curr + 1, 1) + arr[curr][0]);
		ret = max(ret, solve(curr + 1, 0));
	}

	cache[curr][mode] = ret;
	cout << curr << " " << mode << " " << ret << endl;
	return ret;

}


int main() {

	
	int t;
	cin >> t;
	for (int z = 0; z < t; z++) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> arr[i][0];
		}
		for (int i = 0; i < n; i++) {
			cin >> arr[i][1];
		}

		for (int i = 0; i < 100001; i++) {
			for (int j = 0; j < 2; j++) {
				cache[i][j] = -1;
			}
		}

		cout << solve(0, 0) << endl;
		while(1){}
	}
}

djm03178 5년 전 0

반례 드립니다.

1
3
2 5 0
3 5 0
output: 7
correct answer: 8

1
3
0 4 0
3 2 5
output: 9
correct answer: 12

1
3
4 1 1
5 1 4
output: 9
correct answer: 10

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

문제

문제

출처

ICPC

간단한 DP인데 어디가 잘못된걸까요?

freewizard 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말