LIS,Dilworth定理 题意: 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的
展开全文
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
typedef long long ll;
int a[maxn],que[maxn];
int main() {
int n=0,len,i;
展开全文
题目描述 题目链接：https://ac.nowcoder.com/acm/problem/16810某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由
展开全文
题意
有若干发导弹袭来，由于咱们的导弹系统比较拉，当系统打掉一个导弹之后，系统就只能打到与这个导弹高度一样或者低于这个高度的导弹。
第一个问题问你这个系统最多能打掉多少个导弹。
第二个问题问你最少需要多少个系统能把所有的导弹都给打下来。
思路
翻译一下题意就是让咱们找到最长的单调递减子序列，我
展开全文
本题使用动态规划，用dp数组去保存当前数的最长不上升序列长度。那么后面的下一个数的最长不上升序列长度就是前面大于等于这个数的长度中最大的那一个加一。
至于第二问：根据dilworth定理我们知道可划分的最少不上升子序列的数目就是其最长下降子序列的长度。所以求其上升的最长序列即可。
展开全文
题解：此题有两个问题，第一求这套系统最多能拦截多少导弹，第二个求如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 第一个问题即为求最长下降子序列，不多阐述。 对于第二个问题我是用贪心求解的。对于每一个处在i位置的导弹，它可以和（从1到i-1位置且还没有被击落的）任一大于等于其高度的导弹共在一套装
展开全文
题目描述 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度
展开全文
题目描述 链接：https://ac.nowcoder.com/acm/problem/16810来源：牛客网 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导
展开全文
题目 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
