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

vegatrash 4년 전 1

dp[a][b] : a개의 소형 기관차를 이용해 1~b번 열차중에서 적당히 골라 최대한으로 수용할 수 있는 수용량

이라고 정의 하고 풀었습니다..

문제 예시나 제가 만든 각종 테케들은 잘 나오는것 같은데 어떤 반례가 있을까요??

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <time.h>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <set>
using namespace std;

typedef long long ll;

ll dp[4][50001];
ll s[50001];
vector<ll> v;

int main() {
	cin.sync_with_stdio(false);
	cout.sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	v.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		int cap;
		cin >> cap;
		v[i] = cap;
		s[1] = v[1];
		s[i] = s[i - 1] + v[i];
	}
	int k;
	cin >> k;
	for (int i = 1; i <= 3; i++) {
		for (int j = i * 2; j <= n; j++) {
			ll sum = s[j] - s[j - k];
			dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - k] + sum);
		}
	}
	cout << dp[3][n];
}

vegatrash 4년 전 0

40번줄에 i * 2를 i * k라고 바꾸니 맞았습니다.

j = 1부터 시작해도 답은 항상 같게 나오던데 저게 무슨 차이를 가져오는걸까요?

choko100 1년 전 2

안녕하세요, 제 코드의 반례를 랜덤 생성하다가 위의 코드도 잘못된 답이 나오는 반례를 발견하여 공유드립니다.

26 + 44 + 68 이 선택되어야 정답이 나옵니다.

입력

9
26 6 25 18 18 18 4 44 68
1

정답

138

위 코드의 잘못된 출력

137

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

문제

문제

출처

ICPC

★반례★좀 찾아주세요....

vegatrash 4년 전 1

vegatrash 4년 전 0

choko100 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말