글 읽기 - 반례 좀 찾을 수 있을까요 평범한 배낭

kauvoi1011 4년 전 0

질문 검색에 있는 반례들까진 잘돌아가는데 틀렸네요 ㅠㅠ

반례 부탁드려요

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(const vector<int>& A, const vector<int>& B){
	return A[0] < B[0];
}

int main(){
	int N, K;
	int i, j;
	int tK, maxW, maxV, idx;
	vector<vector<int>> a(100+10, vector<int>(2, 0));
	vector<vector<int>> dp(100+10, vector<int>(2, 0));
	
	cin >> N >> K;
	for(i=0; i<N; i++)
		cin >> a[i][0] >> a[i][1];
	
	sort(a.begin(), a.begin()+N, compare);

	dp[0] = a[0];
	for(i=1; i<N; i++){
		tK = K - a[i][0];
		maxW = dp[0][0];
		maxV = dp[0][1];
		idx = -1;
		if(tK < 0)
			continue;
		for(j=0; j<i; j++){
			if(dp[j][0] <= tK && maxV <= dp[j][1]){
				idx = j;
				maxW = dp[j][0];
				maxV = dp[j][1];
			}
		}
		if(idx < 0){
			dp[i] = a[i];
		}
		else{
			dp[i][0] = maxW + a[i][0];
			dp[i][1] = maxV + a[i][1];
		}
	}
	maxV = 0;
	for(i=0; i<N; i++){
		if(maxV < dp[i][1])
			maxV = dp[i][1];
	}
	cout << maxV << '\n';
	
	return 0;
}

vl0612 4년 전 10

ㄴ 인간 노가다 반례입니당~~

5
4
8
3
8
Output : 15
Answer: 16

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

문제

문제

출처

ICPC

반례 좀 찾을 수 있을까요 평범한 배낭

kauvoi1011 4년 전 0

vl0612 4년 전 10

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말