计蒜客 动态规划基础 蒜头跳木桩

题目:

蒜头君面前有一排 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

样例输出

4

思路

不难发现,这时一道 LIS (最长上升子序列)的题目。(当然,这里是最长不上升子序列,其实是一回事。)

O(n2) 复杂度的算法并不能满足全部的数据,所以使用 O(nlogn) 的算法。

O(nlogn) 算法的思路就是储存一个对应 dp 值的最小值,它们一定是升序的。例如标程中将其储存于 ans 数组中,这样,下次有新的最小数出现的时候,利用二分就可以最快找到放入的位置。程序中,变量 pos 是放入 a[i] 的位置,变量 len 就是最长的长度,即为答案。

标程

1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <cstring>
 6 using namespace std;
 7 int n,a[1000+5],dp[1000+5],ans[1000+5],len;
 8 int binarySearch(int arr[], int first, int end, int tar)
 9 {
10     while (end > first)
11     {
12         int mid = (first+end)/2;
13         if (arr[mid]<tar)
14         {
15             end = mid;
16         }
17         else
18         {
19             first = mid+1;
20         }
21     }
22     return end;
23 }
24 int main()
25 {
26     cin >> n;
27     for (int i=1; i<=n; i++)
28     {
29         cin >> a[i];
30     }
31     ans[1] = a[1];
32     len = 1;
33     for (int i=2; i<=n; i++)
34         if (a[i] <= ans[len])
35             ans[++len] = a[i];
36         else
37         {
38             int pos = binarySearch(ans,1,len,a[i]);
39             ans[pos] = a[i];
40         }
41     cout << len << endl;
42     return 0;
43 }

相关推荐