蓝桥杯算法提高VIP-聪明的美食家 （C++代码）

解题思路:

LIS，直接用模板

注意事项:
用dp，难者不会会者不难

参考代码:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define N 1000

using namespace std;

int A[N + 2];
int dp[N + 2];

//dp[i] = max{dp[j] + 1, 1}
int getLIS(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[i] < dp[j] + 1)
				dp[i] = dp[j] + 1;
		}
		ans = max(ans, dp[i]);
	}
	return ans;
}

int main(int argc, char** argv)
{
	int n = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> A[i];
	cout << getLIS(n) << endl;
	return 0;
}