글 읽기 - 반례를 도저히 모르겠어용 ㅠㅠ

gktgnjftm 5년 전 0

올림피아드 문제여서, 정올사이트에다가 내고, 제출했는데도 틀려서

뭐가 틀린지 감이 잘 오질 않습니다 ㅠㅠ

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
#include <string>
#include <math.h>
#include <set>
#include <list>
#include <climits>
#include <string.h>
#include <deque>
#include <functional>
#include <stack>
using namespace std;
typedef long long ll;
#define INF 1000000000
#define mod 1000000007
typedef pair<int, ll> P;
typedef pair<pair<int, int>, int> PP;
typedef pair<int, pair<int, int>> PPP;
int gox[4] = { 0,1,-1,0 };
int goy[4] = { 1,0,0,-1 };
int n,k;
ll dp[105][100005];
vector<P> walk,bike;

ll go(int index,int cnt,int k) {
	if (cnt > k) return -1e9; // 중간에 시간 K보다 커지는 경우(도달불가)
	if (index >= n) return 0; //끝까지 간경우
	ll &ret = dp[index][cnt];
	if (ret != -1) return ret;
	ret = 0;
	ret = max(ret, max(go(index + 1, cnt + walk[index].first, k) + walk[index].second,go(index + 1, cnt + bike[index].first, k) + bike[index].second));// 둘중하나 선택
	return ret;
}
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <=n; i++) {
		ll wti, wmo,bti,bmo;
		scanf("%lld%lld%lld%lld", &wti, &wmo, &bti, &bmo);
		walk.push_back({ wti,wmo });
		bike.push_back({ bti,bmo });
	}
	memset(dp, -1, sizeof(dp));
	printf("%lld\n",go(0,0,k));
	return 0;
}

gktgnjftm 5년 전 0

35번째 줄에 ret=0이 아니라 음의 값을 넣으니까 맞네요..

문제에서 모금액은 자연수라고 명시되어 있어서, 0보다 작은값이 채워질수 없다고 생각하고 쓴건데

혹시 잘알고계시면 명확히 설명해주시면 감사하겠습니다 ^^

djm03178 5년 전 1

그 상황에서 마지막까지 시간 내에 도달하는 것이 아예 불가능한 경우 모금액을 0원으로 반환하게 되면 그 이전까지 채워온 모금액만큼은 모을 수 있다고 판단하는 것과 같습니다. 실제로는 목적지에 도달하는 것이 불가능하기 때문에 이 경우가 고려되지 않아야 합니다.

gktgnjftm 5년 전 0

아 그러네요 엄밀히 생각을못했던부분인거같습니다 정말 감사합니다ㅠㅠ

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

문제

문제

출처

ICPC

반례를 도저히 모르겠어용 ㅠㅠ

gktgnjftm 5년 전 0

gktgnjftm 5년 전 0

djm03178 5년 전 1

gktgnjftm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말