[蓝桥杯][算法提高VIP]聪明的美食家

题目

题目链接

题解

经典动态规划之一。

求最长不下降子序列。 dp[i]表示以第i个数结尾的最长不下降子序列的长度； 转移方程为：dp[i] = max(dp[i], dp[j] + 1)，其中i>j。 含义为：找第i个数之前的数，看是不是不超过第i个数，若是说明可以在找到的这个数后面添加第i个数构成新的子序列，则以第i个数结尾的最长子序列的长度加一。

代码

#include
using namespace std;
const int N = 1e3+10;

int a[N], dp[N], ans, n; 

int main()
{
	cin>>n;
	for(int i = 1;i >a[i], dp[i] = 1;
	for(int i = 1;i