글 읽기 - 2315 예외케이스가 무엇이 있을까요??

stiti 7년 전 0

다이나믹 + 재귀를 사용하였습니다.

dp[i][j] 는 i~j까지 방문했을때의 값입니다.

go(i,j, 지금 있는 위치, 지금 있는 위치의 전력소비량, 흐른 시간)입니다.

예제 케이스는 잘 되는 것 같고, 임의로 몇가지 넣어보았는데 잘 되는 것 같으나, 바로 틀렸습니다가 나오네요

반례가 무엇이 있을까요?

dp[i][j] 상태에서는 dp[i-1][j] 또는 dp[i][j+1]로 상황에 맞게 움직이도록 하였습니다.

#include <iostream>
#include <algorithm>
using namespace std;
int location[1001];
int w[1001];
unsigned long long dp[1001][1001];
int n,k;
unsigned long long go(int i, int j, int now,int weight, int t);
int main()
{
	cin >> n;
	cin >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> location[i] >> w[i];
	}
	cout << go(k, k, location[k], w[k], 0) << endl;
//	for (int i = 1; i <= n; i++)
//		for (int j = 1; j <= n; j++)
//			cout << i << ' ' << j << ' ' << dp[i][j] << endl;
	return 0;
}

unsigned long long go(int i, int j, int now,int weight, int t)
{
	if (i == 1 && j == n) return 0;
	if (dp[i][j]) return dp[i][j];
	if (i > 1 && j < n)
	{
		if (go(i - 1, j,location[i - 1], w[i - 1], t + abs(now - location[i - 1])) + w[i - 1] * (t + abs(now - location[i - 1]))
	> go(i, j + 1,location[ j + 1], w[j + 1], t + abs(now - location[j + 1])) + w[j + 1] * (t + abs(now - location[j + 1])))
			dp[i][j] += go(i, j + 1,location[ j + 1], w[j + 1], t + abs(now - location[j + 1])) + w[j + 1] * (t + abs(now - location[j + 1]));
		else
			dp[i][j] += go(i - 1, j, location[i - 1], w[i - 1], t + abs(now - location[i - 1])) + w[i - 1] * (t + abs(now - location[i - 1]));
	}
	else if (i > 1)
	{
		dp[i][j] += go(i - 1, j, location[i - 1], w[i - 1], t + abs(now - location[i - 1])) + w[i - 1] * (t + abs(now - location[i - 1]));
	}
	else if (j < n)
	{
		dp[i][j] += go(i, j + 1,location[ j + 1], w[j + 1], t + abs(now - location[j + 1])) + w[j + 1] * (t + abs(now - location[j + 1]));
	}
	else return 0;
	return dp[i][j];
}

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

문제

문제

출처

ICPC

2315 예외케이스가 무엇이 있을까요??

stiti 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말