글 읽기 - 가장 긴 바이토닉 부분 수열 반례좀 구해주세요!!!ㅜㅜ

dlwkdgjs 6년 전 0

존경하는 여러분 반례를 구해주실수있나요...?이틀간 이것만 붙잡고있는데도 못찾겠네요....ㅜㅜㅜㅜ 제자신이 너무 한심해보입니다

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

int p[1000];
int dp[1000];
int sub_inc[1000];
int sub_dec[1000];
int pos[1000];

int cal(int n) {
	int max_inc = 0;
	int max_IncIdx = 0;
	int last_concurrent = 0;
	int add = 0;
	int t = 0;
	int sum = 1;
	dp[0] = 1;
	sub_inc[0] = 1;
	sub_dec[0] = 1;
	for (int i = 0; i < n ; i++) {
		int inc = 0;
		int dec = 0;
		for (int j = i; j >= 0; j--) {
			if (p[j] > p[i]) {
				dec = max(dec, sub_dec[j]);
			}
			else if (p[j] < p[i]) {
				inc = max(inc, sub_inc[j]);
			}
		}
			sub_inc[i] = inc + 1;
			sub_dec[i] = dec + 1;
	}


	for (int i = 0; i < n; i++) {
		max_IncIdx = i;///처음부터 제일큰 inc인덱스찾는다
		t = 0;
		add = 0;

		for (int j = i; j >=0; j--) {
			if (p[max_IncIdx] != p[j]) {
				if (sub_inc[max_IncIdx] <= sub_inc[j]) {////앞에있는것들중에서 inc가 가장큰거 찾는다 같을시 마지막기준
					max_IncIdx = j;
				}
			}
		}

		for (int k = i; k >max_IncIdx; k--) {
			if (p[k] > p[i]) {
				add = max(add,sub_dec[i]-sub_dec[k]+1);
			}
			else {
				add = 1;
			}
		}
        sum = max(sum,sub_inc[max_IncIdx]+add );
	}

	
	return sum;
}



int main() {
	int n;
	int r = 0;
	cin >> n;
	if (n == 0) {
		cout << 0;
		return 0;
	}
	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}
	cout << cal(n);
	return 0;
}

doju 6년 전 2

반례입니다.

input
5
1 3 1 2 1

output
4 (1 - 3 - 2 - 1)

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

문제

문제

출처

ICPC

가장 긴 바이토닉 부분 수열 반례좀 구해주세요!!!ㅜㅜ

dlwkdgjs 6년 전 0

doju 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말