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

qalk268 6년 전 0

DP로 풀었고 추적하는 곳에서 distA<=distB도 제출해보았습니다.

남은 거리가 같을때 1부터 보내도 안됩니다

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

int N,W;
int INF = 987564231;
int A[1001],B[1001];
int c[1001][1001];

int dp(int a, int b) {
	if (a == W || b == W) return 0;
		
	int& ret = c[a][b];
	if (ret != -1) return ret;
	ret = INF;

	int next = max(a, b) + 1;
	if (a == 0) { A[0] = 1; B[0] = 1; }
	int distA = dp(next, b) + abs(abs(A[a]-A[next]) + abs(B[a]-B[next]));
	if (b == 0) { A[0] = N; B[0] = N; }
	int distB = dp(a, next) + abs(abs(A[b] - A[next]) + abs(B[b] - B[next]));
	ret = min(distA, distB);

	return ret;
}

void track(int a, int b) {
	if (a == W || b == W) return;
	
	int next = max(a, b) + 1;
	if (a == 0) { A[0] = 1; B[0] = 1; }
	int distA = c[next][b] + abs(abs(A[a] - A[next]) + abs(B[a] - B[next]));
	if (b == 0) { A[0] = N; B[0] = N; }
	int distB = c[a][next] + abs(abs(A[b] - A[next]) + abs(B[b] - B[next]));

	if (distA > distB) {
		cout << 2 << endl;
		track(a, next);
	}
	else {
		cout << 1 << endl;
		track(next, b);
	}

	return;
}

int main() {
	int result = 0;

	cin >> N >> W;
	for (int i = 1; i <= W; i++) {
		cin >> A[i] >> B[i];
	}		
	memset(c, -1, sizeof(c));

	cout<<dp(0, 0)<<endl;
	track(0, 0);

	return 0;
}

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

문제

문제

출처

ICPC

DP 반례 부탁드립니다.

qalk268 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말