[NOIP 1999 提高组] 导弹拦截

Luogu

IDLGP1020

Time1000ms

Memory128MB

DifficultyP4

动态规划 DP贪心1999线段树二分树状数组离散化NOIP 提高组Special JudgeDilworth 定理线性 DP

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 ## Input 一行，若干个整数，中间由空格隔开。 ## Output 两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 [samples] ## Note 对于前 $50\%$ 数据，满足导弹的个数不超过 $10^4$ 个。该部分数据总分共 $100$ 分。可使用 $\mathcal O(n^2)$ 做法通过。对于后 $50\%$ 的数据，满足导弹的个数不超过 $10^5$ 个。该部分数据总分也为 $100$ 分。请使用 $\mathcal O(n\log n)$ 做法通过。对于全部数据，满足导弹的高度为正整数，且不超过 $5\times 10^4$。此外本题开启 spj，每点两问，按问给分。 NOIP1999 提高组第一题 --- $\text{upd 2022.8.24}$：新增加一组 Hack 数据。

Samples

Input #1

389 207 155 300 299 170 158 65

Output #1

6
2

API Response (JSON)

{
  "problem": {
    "name": "[NOIP 1999 提高组] 导弹拦截",
    "description": {
      "content": "某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。     输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP1020"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。\n\n   \n输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。\n\n## I...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments