蒜头君跳木桩(dp)
题目:
蒜头君面前有一排 n 个木桩，木桩的高度分别是h1,h2,h3…hn。蒜头第一步可以跳到任意一个木桩，接下来的每一步蒜头不能往回跳只能往前跳，并且跳下一个木桩的高度 不大于 当前木桩。蒜头君希望能踩到尽量多的木桩，请你帮蒜头计算，最多能踩到多少个木桩。
输入格式
第一行输入一个整数 n 代表木桩个数。第二行输入 n 个整数h1,h2,h3..hn，分别代表 n 个木桩的高度。(1≤n≤1000,1≤hi≤100000)
输出格式
输出一个整数，代表最多能踩到的木桩个数，占一行。
样例输入
6
3 6 4 1 4 2
样例输出
点击查看代码
#include
using namespace std;
int main()
{
int n;
cin >> n;
int a[10000], dp[10000];
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
int ans = 0;
for (int i = 1; i <= n; i++) //跳到i走几步
{
dp[i] = 1; //第一次直接跳i算1次
for (int j = 1; j < i; j++)
{
if (a[j] >= a[i])//比较前面有没有更大的,如果有取dp[j]+1(从前面点一步跳到当前位置)
dp[i] = max(dp[i], dp[j] + 1);
}
ans = max(ans, dp[i]);
}
cout << ans << endl;
}
/*这道题要求长下降子序列
每次跳到第i个格子，都要往前i - 1个格子去找是否有格子的高度大于第i个格子，有的话就步数加一步，
然后每次都要选取最大值。
*/