글 읽기 - 반례좀 찾아주세요...

hash1018 3년 전 0

질문 게시판에 있는 반례를 다 적용해봤고 정답으로 나오는데

또 다른 반례가 있을까요?

#include <vector>
#include <iostream>
#include <cstring>

using namespace std;

int max(int a, int b) {

	if (a > b)
		return a;
	return b;
}

class Object {

private: int w; int v;

public: Object(int w, int v) :w(w), v(v) {} ~Object() {}

		inline int getW() const { return this->w; }
		inline int getV() const { return this->v; }
};

int main(int argc, const char * argv[]) {

	cin.tie(NULL);
	cin.sync_with_stdio(false);

	int n, k;

	cin >> n >> k;

	Object* arr[100001];
	vector<Object*> temp;

	for (int i = 1; i <= n; i++) {

		int w, v;
		cin >> w >> v;
		arr[i] = new Object(w, v);
	}

	int dpValues[100001];
	memset(dpValues, -1, sizeof(int) * 100001);
	vector<int> dpWeights;

	for (int i = 1; i <= n; i++) {

		for (int j = 0; j < dpWeights.size(); j++) {

			int weight = dpWeights.at(j);

			if (weight + arr[i]->getW() <= k) {

				temp.push_back(new Object(weight + arr[i]->getW(), dpValues[weight] + arr[i]->getV()));
			}
		}

		if (arr[i]->getW() <= k) {

			temp.push_back(new Object(arr[i]->getW(), arr[i]->getV()));
		}

		for (int k = 0; k<temp.size(); k++) {

			if (dpValues[temp.at(k)->getW()] == -1) {

				dpWeights.push_back(temp.at(k)->getW());
				dpValues[temp.at(k)->getW()] = temp.at(k)->getV();
			}
			else {

				dpValues[temp.at(k)->getW()] = max(dpValues[temp.at(k)->getW()], temp.at(k)->getV());
			}
		}

		for (int k = 0; k<temp.size(); k++) {
			delete temp.at(k);
		}
		temp.clear();
	}

	int max = 0;

	for (int i = 0; i < dpWeights.size(); i++) {

		int weight = dpWeights.at(i);
		if (dpValues[weight] > dpValues[max]) {
			max = weight;
		}
	}

	cout << dpValues[max] << "\n";


	for (int i = 1; i <= n; i++) {

		delete arr[i];
	}

	return 0;
}

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

문제

문제

출처

ICPC

반례좀 찾아주세요...

hash1018 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말