1557: 蓝桥杯算法提高VIP-聪明的美食家

解题思路:

注意事项:

第一次用的比较暴力的方法，会超时

#include<bits/stdc++.h>
using namespace std;
long long int pre[1005]={0};
long long int dp[1005]={0};
int x[1005]={0};
long long int n;
long long int opt(int i)
{
	if(i==n)return 0;
	if(i==0)return 0;
	if(dp[i]!=0)return dp[i];
	return max(opt(i+1),1+opt(pre[i]));
}
int main()
{
	cin>>n;
	int num=0;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(x[j]>=x[i])
			{
				pre[i]=j;
				break;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(num<(dp[i]=opt(i)))
		{
			num=dp[i];
		}
	}
	cout<<num<<endl;
	return 0;
}

然后在b站学了另外一种方法,

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int f[1005];//当前爽的次数
	int n;
	cin>>n;
	int x[1005];
	f[n]=1;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i];
	}
	for(int i=n;i>=1;i--)//从后面开始
	{
		int num=0;
		for(int j=i+1;j<=n;j++)//遍历第i个数后面的数
		{
			if(x[i]<=x[j])
			{
			    num=max(num,f[j]);//找到后面数中最大爽的次数
			}
		}
		f[i]=num+1;//+1是加上当前的爽
	}
	sort(f,f+n);//找出最爽的
	cout<<f[n-1]<<endl;
	return 0;
}