Problem Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Input
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
Output
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2
题目分析：
炮弹拦截系统其实就是一道经典的最长递增子序列的模板题，对于题目给出的数据，我们依次遍历，首先初始化第一个数为1，因为以第一个数结尾的LIS为1，我们往后遍历，每次遍历的同时，我们在当前数a[i]前面寻找比它小的数但又是小的数里面b[i]最大的数，找到了那我们便在以当前数结尾的LIS加一，同时更新ans的值。循环结束的时候，ans就是我们要求的值
举个例子：
最长递增子序列的可能有很多，但我们只要找到一条即可当前的算法时间复杂度为O(n^2);
dp代码
AC代码
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int a[1005], dp[1005];
int main()
{
int n, ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i)
{
int ma = 0;
for (int j = 1; j < i; ++j)
{
if (a[j] < a[i])
ma = max(ma, dp[j]);
}
dp[i] = ma + 1;
ans = max(ans, dp[i]);
}
printf("%d\n", ans);
return 0;
}
二分代码
优化的代码（非dp）
时间复杂度为nlong(n),我们用二分思想去优化算法。
传送门——理解代码思想
AC代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int a[1005], dp[1005];
int main()
{
int n, ans = 1;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
dp[1] = a[1];
for (int i = 2; i <= n; ++i)
{
if (a[i] > dp[ans])
{
dp[++ans] = a[i];
continue;
} //C++的库函数找区间dp[1]到dp[ans]第一个大于a[i]的数的下标
int x = upper_bound(dp + 1, dp + ans + 1, a[i]) - dp;
dp[x] = a[i];
}
printf("%d\n", ans);
return 0;
}
树状数组代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int a[1005], c[10055];
void add(int i, int v)
{
while (i < 10055)
{
c[i] = max(c[i], v);
i += i & (-i);
}
}
int get(int i)
{
int ans = 0;
while (i)
{
ans = max(ans, c[i]);
i -= i & (-i);
}
return ans;
}
int main()
{
int n, ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]), a[i] += 5; //+5是因为值可能为0，后面不好处理
for (int i = 1; i <= n; ++i)
{
int x = get(a[i] - 1) + 1;
ans = max(ans, x);
add(a[i], x);
}
printf("%d\n", ans);
return 0;
}
| 听说3公里专治心情堵塞，5公里治愈各种忧伤，10公里跑完全是善良和坦然，所以流泪不如流汗~ |
|---|
京公网安备 11010502036488号