HDU - 1257 minimum interception system (dp three methods)

Title Link: [minimum interception system]

General meaning:

One shell of the interception system can reach any height to intercept enemy missiles, but this shell can not exceed the previous height in the future, that is, it can not intercept missiles higher than him again. Then give some missiles and ask how many interception systems are needed at least

Problem solving ideas:

First, it seems to be looking for the decreasing subsequence, but it is the naked of LIS (the longest increasing subsequence). The following explanation:
In the simulation example, first find the longest decreasing sequence X{389300299170158, 65}, remove these numbers, and then find the decreasing sequence Y{207155}. In Y, at least one number a is greater than some numbers in X (otherwise a is smaller than all numbers in x). Therefore, taking a number from each intercepting system can form an increasing subsequence, that is, the number of intercepting systems is equal to the length of the longest increasing subsequence.

There are three ways to find LIS:

1. With the help of LCs (longest common subsequence), first sort the sequence to get A ', then LIS of A is LCS of A and A', complexity O(n2)

2. Use dp to solve LIS. dp[i] represents the length of the longest increasing subsequence ending with the i-th number. dp[i] = max {0, dp [J]} + 1,0 < J < I. the final answer is max{dp[i]}, and the complexity is O(n2)

3. Make clever use of the characteristics of the sequence, count the length of the longest increasing subsequence through an auxiliary array d [] and define the number of len statistical d [] data and the complexity O(nlogn)
Initialize d[1]=h[1], len=1
Operation: process the numbers in H [] one by one. If h[k] is larger than the number at the end of b [], add h[k] to the end of b []. If h[k] is smaller than the number at the end of b [], replace the first number greater than h[k] in d []

AC Code:

//Method 2
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1000;
int h[N], dp[N];
int n;
int LIS() {
	int ans = 1;
	memset(dp, 0, sizeof dp); dp[1] = 1;
	for (int i = 2; i <= n; ++i) {
		int maxx = 0;
		for (int j = 1; j < i; ++j) {
			if (dp[j] > maxx && h[j] < h[i]) maxx = dp[j];
			dp[i] = maxx + 1;
			ans = max(dp[i], ans);
		}
	}
	return ans;
}
int main(void)
{
	while (cin >> n) {
		for (int i = 1; i <= n; ++i) {
			cin >> h[i];
		}
		cout << LIS() << endl;
	}
	return 0;
}

//Method 3
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1000;
int h[N], d[N];
int n;
int LIS() {
	d[1] = h[1];
	int len = 1;
	for (int i = 2; i <= n; ++i) {
		if (h[i] > d[len])d[++len] = h[i];
		else {
			int j = lower_bound(d + 1, d + 1 + len, h[i]) - d;
			d[j] = h[i];
		}
	}
	return len;
}
int main(void)
{
	while (cin >> n) {
		for (int i = 1; i <= n; ++i) {
			cin >> h[i];
		}
		cout << LIS() << endl;
	}
	return 0;
}

END

Tags: C++ Algorithm Dynamic Programming ICPC dp

Posted by mrheff on Tue, 17 May 2022 12:49:43 +0300