yxy

用户名：dotcpp0787179

访问量：497

签　名：

竞赛交流论坛： blog.qzcy2.top 欢迎来撩！

等　　级
排　　名	976
经　　验	3389
参赛次数	3
文章发表	23
年　　龄	1
在职情况	学生
学　　校	内江师范学院
专　　业	纳西妲系

　　自我简介：

我不会

TA的其他文章

杀到这九天十地无人敢称尊,直到身边再无一人能陪我征战,叶天帝不过如此
浏览：38

你可能喜欢

dp动态规划 + 贪心算法 [信息学奥赛一本通T1260-拦截导弹]--NOIP1999 提高组 -- 最详细题解

　　作者: yxy　　　　发表时间：2024-09-19 01:59:59 浏览：65　|　评论：1　

原题链接：信息学奥赛一本通T1260-拦截导弹

# dp 最长上升子序列 模型 额外加一点贪心
###### 本题有两个问题
#### 1.一个防御系统 最多能拦截多少个导弹 
按照题目所说 一个防御系统 只能从最高的往下打 换句话说 也就是求从向往下能打的最多的导弹是多少
###### 仔细一想 就能想到 运用最长上升子序列的模型 求一个反向最长上升子序列（最长下降子序列）
这个好解决 背模板都能秒了；；
## 难点在第二问 如何用最少的防御系统 拦截最多的导弹？？
最开始 我的思路就是 多球几次最长下降子序列 即可求出答案；；很明显 这题不这么简单。%%
##### 换个思路 也许贪心可以解决呢？
我们创建一个数组 用来放每次循环得到的要拦截的导弹的序列的末尾一个 也就是这串序列中位置最低的一个；；
##### 那么 我们每次找到一个 导弹 我们就有两个办法
1.将这个导弹放入前面已经找好的导弹序列的末尾位置 大于该数字的 最小一个；；
~~充分利用空间~~（bushi)
2.找不到 另一个比该导弹位置还高的末尾导弹了 那我们只能重新用一个 防御系统来开头了；；

所以 按照这种思路 我们就有：
###### Code:
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long //个人习惯 有备无患

using namespace std;
const int N = 1010;
int n , q[N] , g[N] , f[N]; // q为存放导弹位置数组 g为个系统所能当前能打到的位置最低的导弹 f为动态规划数组；；

signed main()
{
    while (cin >> q[n]) n ++;  //输入

int res = 0; //存放 第一题答案 最长下降子序列；；
    for (int i = 0 ; i < n ; i ++ ) 
    {
        f[i] = 1;  //每个导弹自己也是一个长度为1 的序列；；
        for (int j = 0 ; j < i ; j ++ ) 
        {
            if (q[i] <= q[j]) f[i] = max(f[i] , f[j] + 1);  //动态转移方程
        }

res = max(res , f[i]);  //更新 答案
    }

cout << res << endl;

int cnt = 0; //刚开始 防御系统的数量为0
    for (int i = 0 ; i < n ; i ++ ) 
    {
        int k = 0; //存放需要的防御系统的最大数量
        while (k < cnt && g[k] < q[i]) k ++; //如果找到一个末尾比当前导弹位置还要矮的 就找下一个系统 如果没有了 就出循环
        g[k] = q[i];
        if (k >= cnt) cnt ++; //找不到新的比当前导弹位置还要高的导弹了 只能新开一个了
    }

cout << cnt << endl;  // 输出答案

return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

109徐守佳

You are the smartest person in the world and do not accept rebuttals

2024-09-20 23:01:32

yxy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

格式错误一万年，，有没有过了的来看看（终于过了）

点我有惊喜！你懂得！

dp动态规划 + 贪心算法 [信息学奥赛一本通T1260-拦截导弹]--NOIP1999 提高组 -- 最详细题解

评论区

精彩推荐

C语言训练-委派任务* （C语言代码）..................竟然是第一个

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言训练-求素数问题（C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

校门外的树（C语言代码）

钟神赛车（C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

yxy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

格式错误一万年，，有没有过了的来看看（终于过了）

点我有惊喜！你懂得！

dp动态规划 + 贪心算法 [信息学奥赛一本通T1260-拦截导弹]--NOIP1999 提高组 -- 最详细题解

评论区

精彩推荐

C语言训练-委派任务* （C语言代码）..................竟然是第一个

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言训练-求素数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

校门外的树 （C语言代码）

钟神赛车 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

　　评论区

C语言训练-求素数问题（C语言代码）

校门外的树（C语言代码）

钟神赛车（C语言代码）