글 읽기 - 질문있습니다. 한 숫자 제거할 때, 어떻게 제거해야할까요?

spearkkk 6년 전 0

한 숫자를 제거해서 최대값을 구하는 문제인데,

저는 우선 최대로 감소되는 부분을 찾아서 0으로 만들어주고 다시 최대합을 구했습니다.

10, -4, 3, 1, 5, 6, -35, 12, 21, -1 일 때, 각 자리에서 뒤의 숫자를 더한 최대합은

21, 11, 15, 12, 11, 6, -2, 33, 21, -1 입니다.

여기에서 증감량을 구하면

10, -4, 3, 1, 5, 8, -35, 12, 22 입니다.

최대로 감소되는 부분 -35인 부분을 제거하고

10, -4, 3, 1, 5, 6, 0(-35제거), 12, 21, -1 구하면 54가 나옵니다.

예제 답은 맞지만, 반례가 있는 거 같습니다.

제 방법이 틀렸을텐데, 어떻게 틀렸을까요?

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
int num[100000];
int cache[100000];
int cache2[100000];

int func(int cur) {
	if (n - 1 == cur) {
		return cache[cur] = num[cur];
	}

	int &ret = cache[cur];

	ret = max(num[cur], num[cur] + func(cur + 1));
	cache2[cur] = cache[cur] - cache[cur + 1];

	return ret;
}

int main() {
	memset(num, 0, sizeof(num));
	memset(cache, 0, sizeof(cache));
	memset(cache2, 0, sizeof(cache2));

	scanf("%d", &n);
	fgetc(stdin);

	for (int i = 0; i < n; ++i) {
		scanf("%d", &num[i]);
		fgetc(stdin);
	}

	func(0);
	//printf("%d\n", *max_element(cache, cache + n));

	int p = min_element(cache2, cache2 + n - 1) - cache2;

	num[p] = 0;

	func(0);

	printf("%d\n", *max_element(cache, cache + n));

	return 0;
}

zlzmsrhak 6년 전 1

제가 알고리즘을 이해한 게 맞다면,

20 -10 1 -50 2 -51 3

부분합 최대를 구하면,

20 -10 1 -50 2 -51 3

가장 많이 감소하는 구간인 -51을 0으로 만들면 답이 20이 나오고,

앞의 -10을 지우면 답이 21이 나옵니다.

spearkkk 6년 전 0

감사합니다 다시 생각해보겠습니다.

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

문제

문제

출처

ICPC

질문있습니다. 한 숫자 제거할 때, 어떻게 제거해야할까요?

spearkkk 6년 전 0

zlzmsrhak 6년 전 1

spearkkk 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말