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

解题思路:

            最长不降子序列和最长上升子序列

#include <iostream>
#include <stdio.h>
#include <map>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 101;
int dp[MAXN];
int ans[MAXN];
int n = 1;
int maxx, num;
void f1()
{
	for (int i = 1; i < n; i++)
	{
		dp[i] = 1;
		for (int j = 1; j < i; j++)
		{
			if (ans[j] > ans[i] && dp[i] < dp[j] + 1)
			{
				dp[i] = dp[j] + 1;
			}
		}
		if (maxx < dp[i])
			maxx = dp[i];
	}
}
void f2()
{
	for (int i = 1; i <= n; i++)
	{
		dp[i] = 1;
		for (int j = 1; j < i; j++)
		{
			if (ans[j] < ans[i] && dp[i] < dp[j] + 1)
			{
				dp[i] = dp[j] + 1;
			}
		}
		if (num < dp[i])
			num = dp[i];
	}
}
int main()
{
	while (cin >> ans[n])
		n++;
	f1();
	memset(dp, 0, sizeof(dp));
	f2();
	cout << maxx << endl << num << endl;
	return 0;
}