글 읽기 - 반례 부탁드릴게요,,,

luok377 4년 전 0

안녕하세요, 제가 Knapsack말고 나름의 논리(?)로 작성하였는데요.

고수님들 괜찮으시면 반례좀 찾아주시면 감사하겠습니다,,,

#include <iostream>
#include <algorithm>

using namespace std;
const int MAX = 105;

int v[MAX];
int w[MAX];

int d[MAX][MAX];

int main() {

	int n, k;
	scanf("%d %d", &n, &k);

	for (int i = 1; i <= n; i++) {
		int w1, v1;
		scanf("%d %d", &w1, &v1);

		w[i] = w1;
		v[i] = v1;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) d[i][j] = v[i];
		}
	}

	for (int i = 1; i <= n; i++) {
		int curHeight = w[i];
		for (int j = i + 1; j <= n; j++) {
			if (curHeight + w[j] > k) {
				d[i][j] = max(d[i][j - 1], d[i][j]);
				if (d[i][j] != d[i][j - 1]) {
					curHeight = w[j];
				}
			}
			else {
				d[i][j] = max(d[i][j - 1], d[i][j - 1] + v[j]);
				if (d[i][j] != d[i][j - 1]) {
					curHeight += w[j];
				}
			}
		}
	}

	int ans = -1;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			//cout << d[i][j] << " ";
			ans = max(ans, d[i][j]);
		}
		//cout << endl;
	}

	printf("%d\n", ans);

	return 0;
}

lucian0910 4년 전 3

반례:

정답: 6
위 코드 사용시 답: 13

luok377 4년 전 0

엇 감사합니다ㅠ

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

문제

문제

출처

ICPC

반례 부탁드릴게요,,,

luok377 4년 전 0

lucian0910 4년 전 3

luok377 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말