笱幼锾

用户名：gyh0416

访问量：3360

签　名：

脑壳疼

等　　级
排　　名	11263
经　　验	1048
参赛次数	0
文章发表	6
年　　龄	0
在职情况	学生
学　　校	湖北文理学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高-能量项链-题解(C语言代码)
浏览：316

你可能喜欢

蓝桥杯算法提高VIP-聪明的美食家-题解(C语言代码)

　　作者: 笱幼锾　　　　发表时间：2020-03-19 07:34:11 浏览：534　|　评论：0　

原题链接：蓝桥杯算法提高VIP-聪明的美食家

###这道题目的本质是 求最大子序列个数
用数组dp保存每个值对应的最优解
i表示上一个满足条件的值
j表示当前正在处理的值
可得状态转移方程为dp[j]=max(dp[j],dp[i]+1)
    #include<stdio.h>
    int ip[1001];
    long dp[1001];
    
    long max(long a,long b)
    {
    	return a>b?a:b;
    }
    
    main()
    {
    	int i,j,n;
    	long value=0,maxsum1=0,maxsum2=0;
    	scanf("%d",&n);
    	for(i=1;i<=n;i++)
    	scanf("%d",&ip[i]);
    
    	for(i=1;i<=n;i++)
    	dp[i]=1;
    
    	for(i=1;i<=n;i++)      //遍历每种可能的情况 
    	for(j=i+1;j<=n;j++)
    	{
    		value=0;
    		if(ip[j]>=ip[i])
    		value=dp[i]+1;    //满足条件则保存该值 
    		dp[j]=max(dp[j],value);  //状态转移方程 
    	}
    	
    	for(i=1;i<=n;i++)
    	if(dp[i]>maxsum1)
    	maxsum1=dp[i];       //找出最大值即题目最优解 
    	
    /*	for(i=1;i<=n;i++)     //看到题目说从一头走到另一头要考虑反方向的情况，后来发现是我想多了 
    	dp[i]=1;
    
    	for(i=n;i>=1;i--)
    	for(j=i-1;j>=1;j--)
    	{
    		value=0;
    		if(ip[j]>=ip[i])
    		value=dp[i]+1;
    		dp[j]=max(dp[j],value);
    //		printf("%d %d %d\n",j,dp[j],value);
    	}
    	
    	for(i=1;i<=n;i++)
    	if(dp[i]>maxsum2)
    	maxsum2=dp[i];*/
    	
    //	printf("%ld",max(maxsum1,maxsum2));
    	printf("%ld",maxsum1);	
    }

0.0分

3 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

笱幼锾

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

字符串的输入输出处理（C语言代码）

点我有惊喜！你懂得！

蓝桥杯算法提高VIP-聪明的美食家-题解(C语言代码)

评论区

精彩推荐

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

printf基础练习2 （C语言代码）

【金明的预算方案】（C++代码）

剪刀石头布（C语言代码）

关于C语言变量位置的问题

1011题解

笱幼锾

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

字符串的输入输出处理 （C语言代码）

点我有惊喜！你懂得！

蓝桥杯算法提高VIP-聪明的美食家-题解(C语言代码)

评论区

精彩推荐

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

printf基础练习2 （C语言代码）

【金明的预算方案】 （C++代码）

剪刀石头布 （C语言代码）

关于C语言变量位置的问题

1011题解

C语言考试练习题_一元二次方程（C语言代码）

字符串的输入输出处理（C语言代码）

　　评论区

【金明的预算方案】（C++代码）

剪刀石头布（C语言代码）