글 읽기 - 반례

seongkwonii 4년 전 0

게시판에 있긴한데 반례를 드디어 찾았네요...

1 1 1 1 1 1

(1)

1 2 2 2 2

(2)

2 2 3 2 2

(3)

5 4 3 2 1

(5)

1 2 3 4 5

(5)

1 2 3 3 2 1

(5인데 저는 6이 나오네요)

제 코드는 나누는 기점?이 하나가 되어야하는데 두 개가 되는게 문제였네요

#include <iostream>
using namespace std;
/*
	1. up_dp를 구한다.
	2. dwn_dp를 구한다.
*/
int n, a[1005], up[1005], dwn[1005];
int up_max, dwn_max;
int main(int argc, char const *argv[]){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i=0; i<n; ++i){
		cin >> a[i];
		up[i] = dwn[i] = 1;
	}
	// up_dp 
	for(int i=0; i<n; ++i){
		for(int j=0; j<i; ++j)
			if( a[i] > a[j] )
				up[i] = max( up[i], up[j] + 1 );

		up_max = max(up_max, up[i]);
	}
	// for dwn_dp
	for(int i=n-1; i>=0; --i){
		for(int j=n-1; j>i; --j)
			if( a[i] > a[j] )
				dwn[i] = max( dwn[i], dwn[j] + 1);
		dwn_max = max(dwn_max, dwn[i]);
	}

	// only up or dwn
	int ans = max(up_max, dwn_max);
	
	// only[i] + dwn[i+1]
	for(int i=0; i<n-1; ++i){
		if( ans < up[i] + dwn[i+1]){ // !!!!!!!!!!!!!!!!!!!!!!!!!!!
			ans = up[i] + dwn[i+1];
			if(up_max == 1 || dwn_max ==1) // this is the point!
				ans -= 1;
		}
	}
	cout << ans << endl;
	
	return 0;
}

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

문제

문제

출처

ICPC

반례

seongkwonii 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말