问题 1557: 蓝桥杯算法提高VIP-聪明的美食家 （动态规划求最长不下降子序列长度）

很简单的动态规划的一个题目

#include <iostream> 
#include <algorithm> 
using namespace std;  
int main() {  
	//freopen("data.in.txt","r",stdin);
	//freopen("data.out.txt","w",stdout);
    int n;  
    cin >> n;  
    int *a = new int [n];  
    int *b = new int [n]; //开辟两个动态数组
    for(int i = 0; i < n; i++)  
    {
        cin >> a[i];  
        b[i]=1;//b[i]表示前i+1个数中的最大不下降子序列的长度  初始值为1 
    }
    for(int i = 0; i < n; i++) {  
        for(int j = 0; j < i; j++) {  
            if(a[i] >=a[j])  //如果a[i]大于等于a[j]，那么最大不下降子序列的长度就会+1
                b[i] = max(b[i], b[j]+1);  //我们取较大的那个
        }  
    }  
    sort(b,b+n);//对数组进行排序
    cout<<b[n-1]<<endl;//输出最大值
    return 0;  
}