HDU1257 최소 차단 시스템 DP/LIS

최장 증자 서열

제목 링크

HDU1257

제목의 뜻

폭탄 차단 시스템이 있다는 얘기다.그것은 매우 특별하다.맞은 n개의 비탄, 높이는ai이다.그는 첫 번째 차단은 임의의 높이에 도달할 수 있지만, 이후에 매번 차단은 반드시 이전 차단의 높이보다 작아야 한다.모두 막아라, 몇 세트의 차단 시스템이 필요한가.

해답하다

방법1: DP

해석하다

우선 우리는 사실 몇 개, 비증가 서열을 구하는지 판단할 수 있다.그리고 하나, 삭제, 하나, 삭제, 이렇게 할 수 있다.그러나 사실 필요 없다. 이 등가는 원 서열의 최장 증자 서열을 구하는 것과 같다.점증하는 원소를 만날 때마다 미사일 시스템을 끊기 때문이다.그리고 너는 모두 차단해야 하기 때문에 가장 긴 점증 서열이다.
그리고 LIS는 DP로 해답을 구할 수 있습니다.dp[i]는 i로 끝나는 가장 긴 증가 서열이 얼마나 길다는 것을 대표한다.상태 이동 방정식은dp[i]=max(0, dp[j])+1, 0 그리고 방법은 이중 순환이다. 각 i점은 그보다 작은 모든 요소를 매거한다.복잡성 O(n)²)

코드

#include
#define ll long long
using namespace std;
const int MAXN = 10000;
int A[MAXN];
int n;
int dp[MAXN];
int LIS()
{
	int ans = 0;
	memset(dp, 0, sizeof(dp));
	dp[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		int max = 0;
		for (int j = 1; j < i; j++)
		{
			if (max < dp[j] && A[j] < A[i])
			{
				max = dp[j];
			}
		}
		dp[i] = max+1;
		if (dp[i] > ans)
			ans = dp[i];
	}
	return ans;
}

int main()
{
	while (~scanf("%d", &n))
	{
		for (int i = 1; i <= n; i++)
			scanf("%d", &A[i]);
		printf("%d
", LIS());	
	}
	return 0;
}

방법2: 활용 성질

해석하다

가장 긴 증자 서열의 길이를 통계하는 데 도움을 줄 d[] 그룹을 만듭니다. (가장 긴 증자 서열이 아닙니다.)초기화는 d[1] = A[1]이다.그리고 A[i]를 읽습니다. 만약에 A[i]가 d[]의 마지막 요소보다 크면.그 다음에 삽입한다.작으면 공교롭게도 A[i]보다 큰 최소 요소를 A[i]로 바꿉니다.(이 단계는 수조의 값을 줄일 수 있다. 네, 가능한 한 서열이 길다.)위치를 찾을 때 2분 검색을 사용하여 복잡도를 log로 낮춥니다.
총 복잡도 O(nlog(n))(나도 책에서 이런 방법을 완전히 이해하는 것은 아니다.)

코드

#include
#define ll long long
using namespace std;
const int MAXN = 10000;
int A[MAXN];
int n;
int dp[MAXN];
int LIS()
{
	int ans = 0;
	memset(dp, 0, sizeof(dp));
	dp[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		int max = 0;
		for (int j = 1; j < i; j++)
		{
			if (max < dp[j] && A[j] < A[i])
			{
				max = dp[j];
			}
		}
		dp[i] = max+1;
		if (dp[i] > ans)
			ans = dp[i];
	}
	return ans;
}

int main()
{
	while (~scanf("%d", &n))
	{
		for (int i = 1; i <= n; i++)
			scanf("%d", &A[i]);
		printf("%d
", LIS());	
	}
	return 0;
}

참고: 알고리즘 경연 입문에서 진급까지