글 읽기 - 반례를 알려주세요

jkb7676 7년 전 0

소스가 많이 더럽긴한데...

반례를 알려주시면 감사하겠습니다.

#include<stdio.h>
typedef struct a{
	int v,a,b;
}aa;

int cal(int a,int b)
{
	if(a>b)return a-b;
	else return b-a;
}
int min(int a,int b )
{
	if(a>b)return b;
	else return a;
}
aa dp[300][300];
int arr[300];
int a,b;
void set()
{
	dp[1][0].v = cal(arr[1],a);
	dp[1][0].a = arr[1];
	dp[1][0].b = b;
	dp[0][1].v = cal(arr[1],b);
	dp[0][1].a = a;
	dp[0][1].b = arr[1];

}
int main()
{
	int i,j,n,k;
	
	scanf("%d",&k);
	scanf("%d %d",&a,&b);
	scanf("%d",&n);
	for(i=1; i<=n; i++)
	{
		scanf("%d",&arr[i]);
	}
	for(i=0; i<=n; i++)
	{
		for(j=0; j<=n; j++)dp[i][j].v = 9999999;
	}
	set();
	for(i=2; i<=n; i++)
	{
		for(j=0; j<=i-2; j++)
		{

			if(dp[i][j].v>min(cal(dp[i-1][j].a,arr[i]),cal(dp[i-1][j].b,arr[i]))+dp[i-1][j].v)
			{
				dp[i][j].v = min(cal(dp[i-1][j].a,arr[i]),cal(dp[i-1][j].b,arr[i]))+dp[i-1][j].v;
				if(cal(dp[i-1][j].a,arr[i])<cal(dp[i-1][j].b,arr[i]))
				{
					dp[i][j].a = arr[i];
					dp[i][j].b = dp[i-1][j].b;
				}
				else
				{
					dp[i][j].a = dp[i-1][j].a;
					dp[i][j].b = arr[i];
				}
			}
			if(dp[i][i-1].v>min(cal(dp[j][i-1].a,arr[i]),cal(dp[j][i-1].b,arr[i]))+dp[j][i-1].v)
			{
				dp[i][i-1].v = min(cal(dp[j][i-1].a,arr[i]),cal(dp[j][i-1].b,arr[i]))+dp[j][i-1].v;
				if(cal(dp[j][i-1].a,arr[i])<cal(dp[j][i-1].b,arr[i]))
				{
					dp[i][i-1].a = arr[i];
					dp[i][i-1].b = dp[j][i-1].b;
				}
				else
				{
					dp[i][i-1].a = dp[j][i-1].a;
					dp[i][i-1].b = arr[i];
				}
			}
			
			if(dp[j][i].v>min(cal(dp[j][i-1].a,arr[i]),cal(dp[j][i-1].b,arr[i]))+dp[j][i].v)
			{
				dp[j][i].v = min(cal(dp[j][i-1].a,arr[i]),cal(dp[j][i-1].b,arr[i]))+dp[j][i].v;
				if(cal(dp[j][i-1].a,arr[i])<cal(dp[j][i-1].b,arr[i]))
				{
					dp[j][i].a = arr[i];
					dp[j][i].b = dp[j][i-1].b;
				}
				else
				{
					dp[j][i].a = dp[j][i-1].a;
					dp[j][i].b = arr[i];
				}
			}
		
			if(dp[i-1][i].v>min(cal(dp[i-1][j].a,arr[i]),cal(dp[i-1][j].b,arr[i]))+dp[i-1][i].v)
			{
				dp[i-1][i].v = min(cal(dp[i-1][j].a,arr[i]),cal(dp[i-1][j].b,arr[i]))+dp[i-1][i].v;
				if(cal(dp[i-1][j].a,arr[i])<cal(dp[i-1][j].b,arr[i]))
				{
					dp[i-1][i].a = arr[i];
					dp[i-1][i].b = dp[i-1][j].b;
				}
				else
				{
					dp[i-1][i].a = dp[i-1][j].a;
					dp[i-1][i].b = arr[i];
				}
			}
	
		}
	}
	int answer= 9999999;

	for(i=0; i<=n-1; i++)
	{

		answer = min(answer,dp[i][n].v);
		answer = min(answer,dp[n][i].v);
	}
	if(answer==9999999)answer = 0;
	printf("%d",answer);
	
}

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

문제

문제

출처

ICPC

반례를 알려주세요

jkb7676 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말