解题思路:
题目的模型就是最长上升子序列模型,是动态规划的基础题。题目含义是给出一串数字,求出按数字从小到大排序的所有组合中所含元素个数最多的组合。
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;
}
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:1205 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:716 |
【偶数求和】 (C语言代码)浏览:646 |
C语言训练-求1+2!+3!+...+N!的和 (C语言代码)浏览:789 |
简单的a+b (C语言代码)浏览:606 |
C语言程序设计教程(第三版)课后习题8.7 (C语言代码)浏览:596 |
2004年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:600 |
小九九 (C语言描述,不看要求真坑爹)浏览:985 |
简单的a+b (C语言代码)浏览:504 |
老王赛马 (C++代码)浏览:905 |