首页 > 其他分享 >[题解] [NOIP 1999] 导弹拦截

[题解] [NOIP 1999] 导弹拦截

时间:2024-04-18 15:26:30浏览次数:24  
标签:结尾 NOIP 1999 题解 mid 序列 长度 拦截 dp

[NOIP 1999] 导弹拦截

题目描述

有若干枚导弹,每一枚导弹的高度是 \(h_i\) ,导弹拦截系统每次拦截导弹都不能比上一次拦截的高度更高,导弹拦截没有冷却时间且第一次拦截的高度任意。

问题1:一套系统最多能拦截多少导弹?

问题2:拦截所有导弹最少需要多少个拦截系统?

输入格式

一行,若干个整数,表示 \(h_i\) 。

输出格式

两行,分别表示两个问题的答案

题解

对于问题1,实际就是求最长不上升子序列的长度,使用动态规划解决。朴素的动态规划是设置 \(dp_i\) 表示以 \(h_i\) 结尾的子序列最大长度。转移时寻找 \(i\) 之前的最大长度转移,即 \(dp_i = max(dp_j), j \leq i 且 h_j \geq h_i\) 。这种算法的时间复杂度是 \(O(n^2)\) ,无法通过。

考虑优化。对每个导弹的枚举显然无法优化,考虑优化状态转移。该算法的瓶颈在于寻找最大长度时需要枚举,但符合高度限制的导弹分布是零散的,无法根据编号快速查找,因此考虑改变查找的维度。我们的目标是获得以 \(h_i\) 结尾的子序列的最大长度,判断是否能往一个序列上延长只需要考虑该序列的结尾元素,而不难得出最大长度会随着子序列结尾的数的减小而增大。换句话说,在取得子序列最大长度的条件下(不论它们的长度是多少),不可能存在h的子序列序列A的结尾元素比子序列B的结尾元素大并且A的长度比B长的情况。因此我们只需要统计出每个长度的不上升子序列的结尾元素即可,在最优情况下,这个结尾元素应该取可能的情况中的最大值。如此我们就得到了一个有序的,可以 \(O(1)\) 验证可行性的序列,采用二分即可在 \(O(log(n))\) 复杂度内找到最优的状态转移。

对于问题2,实际上就是求最长不上升子序列的最少个数,即最长不上升子序列的最小划分。根据 Dilworth 定理,即对于任意有限偏序集,其最大反链中元素的数目必等于最小链划分中链的数目。在本题中的应用是:最长不上升子序列的最小划分数(个数)等于最长上升子序列的长度。因此在第一问的基础上修改得到最长上升子序列的长度即可解决此题。具体的修改是将结尾元素的最大值替换为最小值、验证可行性从不高于变成高于。

AC代码

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 3;

int n, a[MAXN], dp[MAXN], f[MAXN];

int main() {
    while (cin >> a[++n]);
    // 求最长不升子序列
    for (int i = 0; i <= n; i++) f[i] = 0;
    n--;
    int ans1 = 0;
    dp[1] = 1, f[1] = a[1];
    for (int i = 2; i <= n; i++) {
        int l = 1, r = n, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (f[mid] >= a[i]) l = mid + 1;
            else r = mid - 1;
        }
        f[r + 1] = max(f[r + 1], a[i]);
        dp[i] = r + 1;
        ans1 = max(ans1, dp[i]);
    }
    cout << ans1 << '\n';
    // 求最长上升子序列
    int ans2 = 0;
    for (int i = 0; i <= n; i++) f[i] = 1e6;
    dp[1] = 1, f[1] = a[1];
    for (int i = 2; i <= n; i++) {
        int l = 1, r = n, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (f[mid] < a[i]) l = mid + 1;
            else r = mid - 1;
        }
        f[r + 1] = min(f[r + 1], a[i]);
        dp[i] = r + 1;
        ans2 = max(ans2, dp[i]);
    }
    cout << ans2 << '\n';
    return 0;
}

标签:结尾,NOIP,1999,题解,mid,序列,长度,拦截,dp
From: https://www.cnblogs.com/Floyd3265/p/18143561

相关文章

  • LibreOJ-3038 「JOISC 2019 Day3」穿越时空 Bitaro <线段树> 题解
    审题一条链每条边有通行时间上下界限制通过一条边需要\(1\)单位时间站在当前节点时间减少\(1\)耗费\(1\)单位代价\(q\)次询问要么更改一条边的通信时间上下界要么询问在\(b\)时刻在城市\(a\),\(d\)时刻到达城市\(c\)的最小代价思想做题准备......
  • 前端面试题解析与总结
    在2024年的前端行业,面试是进入理想公司的一道门槛。不同公司的面试流程和考察点各有不同,下面将结合三家知名公司的面试题目进行分析和总结,为广大前端开发者提供一份参考指南。一、某对外电商一面:笔试题:弹窗组件防抖截流代码实现关系型数组转换成树形结构对象数组全排列......
  • at_cf17final_j Tree MST 题解
    题目链接点击打开链接题目解法还是挺有收获的题解法1完全图求\(mst\),首先应该考虑\(boruvka\)算法现在的问题转化成了求\(O(\logn)\)次每个点\(x\)到不在\(x\)的连通块中的点的最短边这个可以换根\(dp\)求子树内的是好求的,只要记录所有连通块的最小值和次小值......
  • mongodb启动失败问题解决
    解决办法sudochown-Rmongod:mongod/var/lib/mongochown-Rmongod:mongod/var/log/mongodb/chown-Rmongod:mongod/tmp/mongodb-27017.sock或者可以使用mongod--config/etc/mongod.conf参考:MongoDBloadsbutbreaks,returningstatus=14-AskUbuntumon......
  • AT_abc211_d [ABC211D] Number of Shortest paths 题解
    题目简述给定一张$n$个点$m$条边的无向无权图,问从$1$到$n$的最短路有多少条。题目分析设$cnt_i$表示从$1$到$i$的最短路条数,$dis_i$表示最短路。这道题可以考虑使用BFS做,对于一个点$v$,设第一次更新它的点为$u$,则它的转移应为$cnt_v\leftarrowcnt_u$并......
  • CF81C Average Score 题解
    题目简述给定一个长度为$n$的序列,在其中取出$x$个数,构成一个数列$a$,剩下的$y$个数构成数列$b$。若第$i$个数在数列$a$中,$ans_i$等于$1$,否则等于$2$,请你给出一种方案使得两数列的平均数之和最大且$ans$的字典序最小.题目分析我们先考虑$x=y$的情况,在这种情......
  • ICPC2023杭州站题解(B D E F G H J M)
    本场金牌数量较其他场多(45枚),但金牌线题数不多。五题为分水岭,五道简单题过后所有题均为金牌题,其中有四道可做,即ABEF,做出任意一道即可拿金牌。这里提供除A题以外的所有可做题的题解。ICPC2023杭州站:M:加入比当前选择的所有数大的数一定会让平均值上升,因此答案数列中,V图中的......
  • [题解][洛谷P1136] 迎接仪式
    题目描述对于一个由字母“j”和“z”组成的字符串,可以任意交换两个字符的位置不超过k次,求最多能出现多少个“jz”字串。题解动态规划题。设f[i][j][k][0/1]表示到第i位,前面交换了j个“j”,交换了k个“z”,且第i位是j(用0表示)或z(用1表示)。当j=k时即为可行解。为什么需要用第四维......
  • [题解][洛谷P1108] 低价购买
    题目描述求最长下降子序列长度,以及最长下降子序列的个数。(构成的序列一样的时候,视为同一种最长下降子序列)题解n不超过5000,n^2复杂度即可解决该问题。主要在于如何统计最长下降子序列个数。可以设数组t[i]表示以i为结尾的最长下降子序列个数,在更新f[i]的时候顺便更新。t[i]=......
  • [ABC229E] Graph Destruction 题解
    [ABC229E]GraphDestruction题解思路解析题目要求删点,而众所周知删点的代价要大于加点的代价,于是我们考虑倒着处理询问,将每一个删点改成加点,而加点时就用并查集维护连通块即可。code#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+10;intn,m,fa[N];......