描述
Redraiment是走梅花桩的高手。Redraiment可以选择任意一个起点,从前到后,但只能从低处往高处的桩子走。他希望走的步数最多,你能替Redraiment研究他最多走的步数吗?
数据范围:每组数据长度满足1≤n≤200 , 数据大小满足 1≤val≤350
输入描述:
数据共2行,第1行先输入数组的个数,第2行再输入梅花桩的高度
输出描述:
输出一个结果
示例1
输入:
6
2 5 1 5 4 5
输出:
3
说明:
6个点的高度各为 2 5 1 5 4 5
如从第1格开始走,最多为3步, 2 4 5 ,下标分别是 1 5 6
从第2格开始走,最多只有1步,5
而从第3格开始走最多有3步,1 4 5, 下标分别是 3 5 6
从第5格开始走最多有2步,4 5, 下标分别是 5 6
所以这个结果是3。
解题思路:
这道题我是利用动态规划来写的,动态规划yyds
用动态规划有两个关键点:状态转移方程;边界条件
这里我设dp[i]为从第0格到第i格的最大步数(注意:并不是非得从第0格开始,0到i之间的任意位置开始即可,只要值是最大的,就比如上述的示例1)
边界条件很简单,就是dp[0],显然它的值为1。
举个栗子:
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
height[i] |
1 |
2 |
3 |
2 |
6 |
7 |
1 |
8 |
9 |
12 |
13 |
dp[i] |
1 |
2 |
3 |
2 |
4 |
5 |
1 |
6 |
7 |
8 |
9 |
最后遍历dp数组,其中最大的值就是Redraiment走的最多步数。
代码如下:
#include <stdio.h>
#define N 200
int main()
{
int i,j,cnt,height[N],dp[N],max=1;
scanf("%d",&cnt);
for(i=0;i<cnt;i++)
{
dp[i]=1; //每个位置的步数都初始化为1
scanf("%d",&height[i]);
for(j=0;j<i;j++) //遍历之前位置的高度和步数值
{
if(height[j]<height[i]&&dp[j]+1>dp[i]) //如果当前高度大于之前某个位置的高度,
dp[i]=dp[j]+1; //且之前那个位置的步数加1能够大于
} //当前位置的步数,则更新当前位置的步数
}
for(i=0;i<cnt;i++)
{
if(dp[i]>max) //遍历dp数组,其中的最大值就是在之前某一位置跳到该最大值位置的步数
max=dp[i];
}
printf("%d\n",max);
return 0;
}