글 읽기 - 반례를 못찾겠습니다.

sik8856 4년 전 0

코드를 구현 할때

dp를 사용해서 아래와 같이 구현하였습니다.

처음과 2번째를 초기화 하고 최대값을 사용해서 최적의 해를 구했습니다.

게시판의 반례와 예시는 모두 맞는거같은데 어디서 틀리는지 알수가 없습니다.

도와주세요 ㅠㅠ

#include <iostream>
#include <vector>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

int t;
int arr[1002] = {0,};
int ans[1002] = {0,};
int main() {
	
	int n;	
	cin >> n;

	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		arr[i] = a;
	}
	ans[1] = arr[1];
	ans[2] = max(arr[1] + arr[1], arr[2]);

	for (int i = 3; i <= n; i++) {
		ans[i] = max(arr[i], ans[i - 1] + arr[1]);
		if (i % 2 == 0) {
			ans[i] = max(ans[i], ans[i / 2] + ans[i / 2]);
		}
		else {
			ans[i] = max(ans[i], ans[(i / 2) +1] + ans[i / 2]);
		}

	}
	
		cout << ans[n] << endl;

	

	
	

	
}

meringueee 4년 전 1

1 10 1 1 1 1

정답은 2장짜리 세 번 사서 30이지만

작성하신 로직대로면 22가 나올 것 같아요

skysign 3년 전 0

문제 풀이 입니다. 도움이 되셨으면 좋겠네요.

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.

sik8856 4년 전 0

meringueee 4년 전 1

skysign 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말