聪明的美食家

解题思路:
题目的模型就是最长上升子序列模型，是动态规划的基础题。题目含义是给出一串数字，求出按数字从小到大排序的所有组合中所含元素个数最多的组合。

3 18 7 14 10 12 23 41 16 24中 3 7 10 12 23 41是元素个数最多的组合方式。

状态转移方程dp[i]代表以第i个数为结尾吃的爽的最多次数，i从1枚举到n(小吃街上小吃的数量)

假设当前枚举到第i个数,那么根据题意dp[i]应该是前i个数中包含元素最多的组合，那么为了保证dp[i]这个组合是含元素最多的解，那么必须确保这个dp[i]组合中以倒

数第二个元素为结尾的子组合也必须是最优解，为了确定以倒数第二个元素为结尾的组合是最优解我们需要对1~i-1的dp[i]选取最优解 dp[i]=max(dp[i],dp[j]+1);

参考代码:

#include <stdio.h>

#define max(a,b) ((a)>(b)?(a):(b))

int main(){

int a[50],dp[50];

int n;

int maxsum=1;

scanf("%d",&n);

for(int i=1;i<=n;i++)

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

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

dp[i]=1;

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

if(a[j]<a[i])

dp[i]=max(dp[i],dp[j]+1); 

}

if(dp[i]>maxsum)

      maxsum=dp[i];       

}

printf("%d",maxsum);  

return 0;

}