글 읽기 - lis,lds로 풀었는데 그냥 바로 틀립니다 혹시 잘못된점 지적해주실수있으신가요?

isvara 4년 전 0

i부터 시작하는 lis lds를 구하고 저장을 시킨 다음 lis+lds-1로 구했습니다.

혹시 코드 잘못된게 있을 까요 ㅜ?

#include<iostream>
#include<vector>
#include<math.h>
#include<cstring>
#include<queue>
#include <cstdio>
#include<utility>
#include <algorithm>
#include<string>
#include<set>
#include<list>
#include<functional>
using namespace std;

int N;
vector<int> weight;
vector<int>res;
int cache[2001];
int LDS[2001];
int LIS[2001];
const int INF = 98765431;

int binary_search(int lo, int ro, int target)
{
	int ans = INF;
	int mid;
	while (lo < ro)
	{
		mid = (lo + ro) / 2;

		if (res[mid] > target)
			lo = mid + 1;
		else if (res[mid] < target)
			ro = mid;
	}
	return mid;
}
int lds(int start)//자기자신을 제외한 
{
	res.clear();
	res.push_back(INF);

	for (int i = start; i < N; i++)
	{
		int key = weight[i];
		
		//!
		if (weight[start] < key)
			continue;

		if (res.back() >= key)
			res.push_back(key);
		else
		{
			int index=binary_search(0, res.size() - 1, key);
			res[index] = key;
		}
	}
	return res.size() - 1;
}
int lis(int start)
{
	res.clear();
	vector<int>res;
	res.push_back(-INF);
	for (int i = start; i < N; i++)
	{
		int key = weight[i];

		//!
		if (weight[start] > key)
			continue;

		if (res.back() < key)
			res.push_back(key);
		else
		{
			vector<int>::iterator iter = lower_bound(res.begin(), res.end(), weight[i]);
			*iter = weight[i];
		}
	}
	return res.size() - 1;
}
int main()
{
	int ans = 0;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int tmp;
		cin >> tmp;
		weight.push_back(tmp);
	}
	for (int i = 0; i < N; i++)
	{
		LDS[i] = lds(i);
		LIS[i] = lis(i);
	}
	for (int i = 0; i < N; i++)
		ans = max(ans, LDS[i] + LIS[i] - 1);

	cout << ans;
}

pichulia 4년 전 0

binary search가 잘못됬습니다.

100 99 98 3 2 1 50 49 48 47

위의 데이터를 테스트해보시기 바랍니다.

lo=0, ro=2 일 때 res[1] > target인 경우 무슨 일이 벌어지는지 확인해보시고, 이것이 원하는 동작이 맞는지 확인바랍니다.

chogahui05 4년 전 0

이거 답이 5일까요?

앞에 추가되고 뒤에 추가되고는 잘 모르겠지만.. 어떠한 친구가 추가되기 시작했다면

a ta ta' ta'' ta'''

단, a<ta<ta'이고

ta'''<ta''<a꼴이면 저게 성립하겠죠. 즉, LIS와 LDS를 구함 되는 건데.. 뭘 포함하는?? arr[i]에서 시작하는..

455에서 출발했을 시, 최대 LDS는, 455 - 319 - 314 - 183 - 101입니다. 길이가 5네요.

다음 455에서 출발했을 시, 최대 LIS는 455 - 605 - 861로 3입니다.

이 수들을 순서대로 모아보면 455 - 319 - ... - ... - 314 - 183 - 605 - ... - 861 - 101 - ... - ... - ... 인데

455

319 (B)

314 (B)

183 (B)

605 (F)

861 (F)

101 (B)

에 놓으면 7개 되나요? 왜 5가 출력될까용??

13
455 319 64 159 314 183 605 884 861 101 298 571 301

chogahui05 4년 전 1

하나 팁 드리자면 LDS는 어떻게 보면 내림차순으로 하는 건데

a<b라면 -a>-b임을 이용하신다면, lower_bound로도 충분히 구현하실 수 있습니다.

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

문제

문제

출처

ICPC

lis,lds로 풀었는데 그냥 바로 틀립니다 혹시 잘못된점 지적해주실수있으신가요?

isvara 4년 전 0

pichulia 4년 전 0

chogahui05 4년 전 0

chogahui05 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말