글 읽기 - 반례를 알 수 있을까요..

a99azaz 3년 전 0

dp[x][y] 를 자신을 떼고 왼쪽으로 지그재그로 떼거나 자신을 떼고 바로 왼쪽에 있는걸 안떼고 그것의 왼쪽에 있는걸 떼는 것 중 큰 걸로 했습니다.

마지막(가장 오른쪽) 것을 안떼는 경우는 없으니 로직은 맞는거 같은데.. 어디가 잘못되었을까요?

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

int dp[2][100000];
int s[2][100000];

int main()
{
	cin.tie(NULL); cout.tie(NULL);
	ios::sync_with_stdio(false);

	int t, n;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		cin >> n;

		for (int z = 0; z < 2; z++)
		{
			for (int j = 0; j < n; j++)
				cin >> s[z][j];
		}

		dp[0][0] = s[0][0];
		dp[1][0] = s[1][0];
		dp[0][1] = s[1][0] + s[0][1];
		dp[1][1] = s[0][0] + s[1][1];

		for (int z = 2; z < n; z++)
		{
			dp[0][z] = max(s[0][z] + s[1][z - 1] + dp[0][z - 2], s[0][z] + dp[1][z - 2]);
			dp[1][z] = max(s[1][z] + s[0][z - 1] + dp[1][z - 2], s[1][z] + dp[0][z - 2]);
		}

		cout << max(dp[0][n - 1], dp[1][n - 1]) << '\n';
	}
	return 0;
}

p_ce1052 3년 전 0

죄송합니다 잘못 반례를 드려서 삭제했습니다

p_ce1052 3년 전 3

진짜 반례입니다

1 4

100 1 1 100

1 1 100 1

답 : 300

출력 : 202

a99azaz 3년 전 0

감사합니다!! 아직 멀었네요.. ㅋㅋㅋ

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

문제

문제

출처

ICPC

반례를 알 수 있을까요..

a99azaz 3년 전 0

p_ce1052 3년 전 0

p_ce1052 3년 전 3

a99azaz 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말