글 읽기 - 반례 부탁드립니다.

dhtmdgus2134 3년 전 0

예시는 다 맞는데 2퍼에서 틀리네요 ..

앞에서 부터 현제 위치에서 거리만큼 떨어진 곳의 DP와 현제 위치의 DP와 값을 더한것 중에서 큰 값을 산출하는 방식으로 했구요

반드시 다음 날짜를 선택 하지 않아도 되기 때문에 현제 DP값이 없는 곳은 이전 DP 값을 끌어와서 사용하도록 했습니다

#include<iostream>
#define MAX 16

using namespace std;
int tc,top;
int DP[MAX];
int arr[MAX][2];
int max(int a, int b) {
	return a > b ? a : b;
}
int work() {
	for (int i = 0; i < tc; i++) {
		if (tc < arr[i][0] + i) continue;
		if (DP[i] == 0) {
			int f = i;
			while (!DP[i] && f>0) {
				if (DP[f])
					DP[i] = DP[f];
				f--;
			}
		}
		DP[i + arr[i][0]] = max(DP[i] + arr[i][1], DP[i + arr[i][0]]);

		if (top < DP[i + arr[i][0]])
			top = DP[i + arr[i][0]];
	}
	return top;
}
int main(void) {
	cin >> tc;
	for (int i = 0; i < tc; i++) {
		cin >> arr[i][0] >> arr[i][1];
	}
	cout << work();
	
}

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

문제

문제

출처

ICPC

반례 부탁드립니다.

dhtmdgus2134 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말