글 읽기 - 반례좀부탁드려요..

jkb7676 7년 전 0

분명 문제가있는건 확실한데 뭔지모르겠어요.

고수님들의 빠른답변 부

#include<stdio.h>

int dp[501][501];
int arr[501];
int max;
int max1(int a,int b)
{
	if(a>max&&b>max)return -1;
	if(a<0&&b<0)return -1;
	if(a>max&&b<max)return b;
	else if(a<max&&b>max)return a;
	else if(a>b)return a;
	else return b;
}
int main()
{
	int i,j,n,k;
	int s;
	scanf("%d %d %d",&n,&s,&max);
	for(i=1; i<=n; i++)
	{
		scanf("%d",&arr[i]);
	}
	
	dp[1][0] = max1(dp[1][0],s+arr[1]); //첫번째노래를 +
	dp[0][1] = max1(dp[0][1],s-arr[1]); //첫번째노래를 - 
	//dp[i][j] = i번째노래를 + ,j번째 노래를 -
	for(i=2; i<=n; i++)
	{
		for(j=0; j<=i-2; j++)
		{
			dp[i][j] = max1(dp[i][j],dp[i-1][j]+arr[i]);
			dp[i][i-1] = max1(dp[i][i-1],dp[j][i-1]+arr[i]);
			//+하는경우
			dp[j][i] = max1(dp[j][i],dp[j][i-1]-arr[i]);
			dp[i-1][i] = max1(dp[i-1][i],dp[i-1][j]-arr[i]);
			//-하는경우 
		}
	}
	
	int answer = -1;
	for(i=0; i<=n-1; i++)
	{
		answer = max1(answer,dp[i][n]);
		answer = max1(answer,dp[n][i]);
		printf("%d %d\n",dp[i][n],dp[n][i]);
	}
	 printf("%d",answer);
}

methylene 7년 전 0

반례입니다.

4 10 25
10 10 10 10

정답이 10인데

출력이 20이네요

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

문제

문제

출처

ICPC

반례좀부탁드려요..

jkb7676 7년 전 0

methylene 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말