首页 > > 程序设计 > C/C++ >

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

2018-06-17 21:45:46来源：未知阅读 ()

题目：

蒜头君面前有一排 n 个木桩，木桩的高度分别是h₁,h₂,h₃?h_n??。蒜头第一步可以跳到任意一个木桩，接下来的每一步蒜头不能往回跳只能往前跳，并且跳下一个木桩的高度不大于当前木桩。蒜头君希望能踩到尽量多的木桩，请你帮蒜头计算，最多能踩到多少个木桩。
输入格式

第一行输入一个整数 n 代表木桩个数。第二行输入 n 个整数h₁,h₂,h₃?h_n，分别代表 n 个木桩的高度。(1≤n≤1000,1≤h_i≤100000)

输出格式

输出一个整数，代表最多能踩到的木桩个数，占一行。

样例输入

6
3 6 4 1 4 2

样例输出

4

思路

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

O(n²) 复杂度的算法并不能满足全部的数据，所以使用 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 }