解题思路:
题目的模型就是最长上升子序列模型,是动态规划的基础题。题目含义是给出一串数字,求出按数字从小到大排序的所有组合中所含元素个数最多的组合。
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.4 (Java代码)浏览:1416 |
求圆的面积 (C语言代码)浏览:1267 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:548 |
大神老白 (C语言代码)浏览:640 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:661 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:510 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:664 |
Tom数 (C语言代码)浏览:725 |
C二级辅导-同因查找 (C语言代码)浏览:563 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:498 |