大一菜鸡路过，求大佬带

解题思路:此题是一道坐标型动态规划问题，实质是最长上升子序列，但要注意的是此题中只要下一次吃的食物不比本次差，即下一次的食物美味程度food[i] >= food[j](i > j)，则每个美味程度都对应一个爽的程度: happy[i], 并且每一个happy[i]都可以按以下方法表示， happy[i] = max{ happy[i],  happy[j] + 1(food[i] >= food[j]) }, 如果在food[i]之前找不到比它小的food[j], 那么happy[i]就是它本身，也就是1，因为此时它本身就是一个最长上升字串，如果food[i]之前存在比它小的food[j], 那么此时上升字串就是food[j]对应的上升字串加1， 如果这个值大于happy[i]本身，那么就更新happy[i], 最后找出happy[i]的最大值

注意事项:不同于最长上升子序列，这里的条件是美味程度 >= 前一个即可

参考代码:

#include<stdio.h>

int max(int a, int b)

{

if (a > b)

    return a;

return b;

}

int main()

{

int n;

scanf("%d", &n);

int food[n],happy[n];

int max_happy = 0;

for (int i = 0; i < n; ++i) {

scanf("%d", &food[i]);

}

for (int i = 0; i < n; ++i) {

happy[i] = 1;//赋初值

for (int j = 0; j < i; ++j) {

if (food[j] <= food[i]) {

happy[i] = max(happy[j] + 1, happy[i]);//更新状态

}

max_happy = max(max_happy, happy[i]);//更新最大值

}

}

printf("%d\n", max_happy);

return 0;

}