蓝桥杯算法训练VIP-拦截导弹 （C++代码）

解题思路

实际上就是一个最长不递增子序列问题，最多拦截数好求，但是拦截次数怎么求呢？看了一下题解才有思路的，拦截次数问题和最多拦截数其实就是相对的问题，虽然并不知道为什么。内层循环的符号改一下就可以了

注意事项:

测试数据比较水，量很小

参考代码:

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <stdio.h>
#include <memory.h>
#define N 15

using namespace std;

int dp[N + 2];
vector<int> A;

int solve1(int n)
{
	int ans = -1;
	for (int i = 1; i <= n; i++)
	{
		dp[i] = 1;
		for (int j = 1; j < i; j++)
			if (A[j] >= A[i] && dp[j] + 1 > dp[i])
				dp[i] = dp[j] + 1;
		ans = max(ans, dp[i]);
	}
	return ans;
}

int solve2(int n)
{
	int ans = -1;
	for (int i = 1; i <= n; i++)
	{
		dp[i] = 1;
		for (int j = 1; j < i; j++)
			if (A[j] < A[i] && dp[j] + 1 > dp[i])
				dp[i] = dp[j] + 1;
		ans = max(ans, dp[i]);
	}
	return ans;
}

int main()
{
	int n = 0;
	int temp = 0;
	A.push_back(0);//填充，无实义
	while (cin >> temp)
	{
		A.push_back(temp);
		n += 1;
	}
	cout << solve1(n) << endl;
	memset(dp, 0x00, sizeof(dp));
	cout << solve2(n) << endl;
	return 0;
}