글 읽기 - 도데체 반례를 아무리 봐도못찾겠어요

dlwkdgjs 7년 전 0

반례 좀 찾아줘요

정답 소스랑 비교해서 반례찾으려고 노력해도 안대요

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

int dp[1015];
int p[1015];
int sub[1015];

int cal(int n) {
	int last = 0;
	int temp = 0;
	fill_n(sub, n, 1);

	dp[0] = 1;
	sub[0] = 1;
	if (p[1] > p[0]) {
		last = 1;
		dp[1] = 2;
		sub[1] = 2;
	}
	else {
		last = 0, dp[1] = 1;
		sub[1] = 1;
	}

	for (int i = 2; i < n; i++) {
		if (p[last] < p[i]) {
			last = i;
			dp[i] = dp[i - 1] + 1;
			sub[i] = sub[i - 1] + 1;
		}
		else {

			for (int j = i - 1; j >= 0; j--) {
				if (p[i]>p[j]) {
					sub[i] = max(sub[i], sub[j] + 1);
				}
			}

		}

		if (dp[last] < sub[i]) {
			dp[i] = sub[i];
			last = i;
		}
		else {
			dp[i] = dp[last];
		}
	}

	return dp[n - 1];
}

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