域名有了怎么制作网站,免费收录平台,wordpress 歌曲列表,长春建设招标网P1020 [NOIP1999 普及组] 导弹拦截 前言题目题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示题目分析注意事项 代码动态规划#xff08;NOIP要求#xff1a;时间复杂度O(n^2^)#xff09;贪心二分#xff08;O(nlgn)#xff09; 后话额外测试用例样例输入 #1… P1020 [NOIP1999 普及组] 导弹拦截 前言题目题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示题目分析注意事项 代码动态规划NOIP要求时间复杂度O(n^2^)贪心二分O(nlgn) 后话额外测试用例样例输入 #1样例输出 #1样例输入 #2样例输出 #2 王婆卖瓜 参考来源 前言
再做几题动态规划我们就去做图搜索另外最近要期中考因为还是需要绩点的所以断更几天。期中考后应该就开始图搜索算法啦 隐约记得这题当作期末或者期中考的题目应该是算法的至少当时我是没有做出来的现在我凭自己的实力做出来了O(n2)虽然没有很快做出来卡了好久但是至少进步是很明显的然后又学习了一下贪心的思想也是做出来O(lgn)希望跟着我刷题的宝子们跟着我的进度也能有大的进步
题目
题目描述
某国为了防御敌国的导弹袭击发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷虽然它的第一发炮弹能够到达任意的高度但是以后每一发炮弹都不能高于前一发的高度。某天雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段所以只有一套系统因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度计算这套系统最多能拦截多少导弹如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行若干个整数中间由空格隔开。
输出格式
两行每行一个整数第一个数字表示这套系统最多能拦截多少导弹第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
样例 #1
样例输入 #1
389 207 155 300 299 170 158 65样例输出 #1
6
2提示
对于前 50 % 50\% 50% 数据NOIP 原题数据满足导弹的个数不超过 1 0 4 10^4 104 个。该部分数据总分共 100 100 100 分。可使用 O ( n 2 ) \mathcal O(n^2) O(n2) 做法通过。 对于后 50 % 50\% 50% 的数据满足导弹的个数不超过 1 0 5 10^5 105 个。该部分数据总分也为 100 100 100 分。请使用 O ( n log n ) \mathcal O(n\log n) O(nlogn) 做法通过。
对于全部数据满足导弹的高度为正整数且不超过 5 × 1 0 4 5\times 10^4 5×104。
此外本题开启 spj每点两问按问给分。 upd 2022.8.24 \text{upd 2022.8.24} upd 2022.8.24新增加一组 Hack 数据。
题目分析 抛开第二问我们先来关于第一问也就是第一行的输出。 题目第一问很明显是一个最长非递增子序列的计算或者说最长非严格递减子串。我给出了两个方法一个是动态规划但是由于我的技术不精或者说确实没办法只能达到O(n2)。另一种是贪心二分就可以达到O(nlgn)。 首先介绍一下动态规划方法与我前面的挖地雷类似首先找到数值变化的点在哪显然是找到一个更小的值可以加到这个非递增子序列上。但是我们需要找到最好的值所以我们建立一个f数组用来存储当前节点的最好结果然后我们遇到下一个点的时候就可以更新包括这个节点的最好结果如此下去直到最后一个节点然后遍历整个f数组找到最好的值输出。具体代码见下方但是不足是时间复杂度不太行 接着我们思考贪心的算法贪心好像需要满足一个前提条件局部最优解是全局最优解的一部分我这里就不证明了(我也不太会)。直接来看贪心的思想。对于每个数既可以把它接到已有的导弹拦截后面也可以建立一个新系统。要使子序列数最少应尽量不建立新序列。另外应让每个导弹系统的末尾尽可能大这样能接的数更多。因为一个数若能接到小数后面必然能接到大数后面反之则不成立。我们维护一个栈用来表示最长非递增子序列根据贪心算法的思想这个栈的维护需要做到以下两点1.比栈顶小的数直接入栈2.找到栈里最小的大于该数的元素将这个元素替换成这个数。又因为这个栈是从大到小排序所以我们找位置的时候可以使用二分查找来节省时间。代码也是看下方。 接着就是解决第二问的问题首先需要引入一个Dilworth定理: Dilworth定理对于任意有限偏序集其最大反链中元素的数目必等于最小链划分中链的数目。 换句话讲最长上升子序列的长度就是能构成的不上升序列的个数。于是系统求个数其实就是求最长递增子序列或者说LIS的长度然后按照上面的方法修改一下大于和小于等于号就可以了是不是很奇妙所以这题还是很有难度的但凡你不知道这个定理想要做出来不是一件容易的事情。
注意事项
1.输入没有给定长度的处理办法 C
int x,n-1;
while(cinx)a[n]x;n;//从0开始n表示个数int x,n0;
while(cinx)a[n]x;//从1开始n表示个数//不知道为什么while(cina[n]);不行C语言
while(~scanf(%d,a[n])); --n;
while (scanf(%d, a(n)) ! EOF) ; --n;python(待补充)
#有没有帅哥美女知道的评论区告诉我一下2.注意是最长非严格递减数列所以是可以包括等于的情况判断时应该是a[j]a[i]
3.二分法while里面记得判断条件是a[i]f[mid]有个笨蛋写成a[i]f[point]了。
代码
动态规划NOIP要求时间复杂度O(n2)
NOIP的要求是O(n2)所以我们可以使用动态规划过前十个点的数据
#includeiostream
using namespace std;
int a[100007] {0},path[27] {0},f1[100007] {0},f2[100007] {0};
int main()
{int n-1,maxx0,minn0,flag10,flag20,x;while(cinx)a[n]x;n;f1[0]1;f2[0]1;for(int i1; in; i) {maxx0;minn0;//每次都要重新初始化for(int j0; ji; j) {if(f1[j]maxxa[i]a[j]) {//找到符合条件的最大值maxxf1[j];}if(f2[j]minna[i]a[j]) {minnf2[j];}}f1[i]maxx1;f2[i]minn1;}int ans10,ans20;for(int i0; in; i) {if(f1[i]ans1)ans1f1[i];if(f2[i]ans2)ans2f2[i];}coutans1endlans2;return 0;
}贪心二分O(nlgn)
本法巧妙利用了贪心的性质并且用二分法来查找最大值将时间复杂度打到O(nlgn)。 并且有个偷懒的地方是使用了一个判断函数将两个计算子串长度的函数合并成一个 栈还保存了最长上升或递减子序列的列表 噔噔噔代码闪亮登场
#includeiostream
using namespace std;int a[100007] {0},f[100007] {0};
void test(int f[],int x){//没有用就是用来测试的 for(int i 1; ix;i){coutf[i] ;}coutendl;
}
bool relation(int x,int y,int rela)//用来返回判断值的
{if(rela1) {return xy;} elsereturn xy;
}
int Lg_sequence(int n,int rela)//计算相反的两个最长子串
{int f[100007] {0};int point1;f[1]a[0];for(int i 1 ; i n ; i ) {if(relation(a[i],f[point],rela)) {//符合子串直接入栈 f[point]a[i];} else {int l 1, r point;while (l r) {//找到大于该值的最小的栈值 int mid (l r) 1;if (relation(a[i],f[mid],!rela)) {r mid;} else {l mid 1;}}f[l] a[i];}}return point;
}
int main()
{int n-1,maxx0,minn0,point1,x;while(cinx)a[n]x;n;//n表示数组长度 coutLg_sequence(n,0)endlLg_sequence(n,1);return 0;
}后话
额外测试用例
因为太笨获得了两个测试用例
样例输入 #1
330 309 267 287 315 380 365 363 364 351 316 381 355 372 289 284 356 299 369 361 327 372 360 282 327 280 258 293 258 254 298 320 324 314 273 340 251 324 327 339 270 248 275 318 321 283 293 341 247 321 318 270 328 322 294 299 259 304 302 286 287 239 333 300 269 240 269 275 296 292 254 308 325 285 218 282 221 288 238 307 212 263 316 300 264 278 215 304 306 296 218 206 225 206 266 250 288 208 241 297 264 211 285 294 236 206 292 215 249 195 206 202 198 276 258 199 192 207 195 261 253 212 206 214 269 234 254 250 196 246 244 227 229 238 194 221 192 243 181 233 180 242 206 247 223 195 187 210 181 176 214 201 209 207 231 222 199 217 212 222 197 168 217 195 193 216 163 203 163 230 206 201 153 184 177 193 174 189 175 155 148 197 184 201 169 155 182 166 156 202 204 193 143 199 167 194 174 195 181 171 163 170 173 169 184 160 130 132 166 128 160 149 140 182 144 127 140 175 134 175 146 169 159 176 152 118 131 120 156 119 141 144 121 146 116 160 136 116 123 135 109 158 127 115 127 148 116 126 140 109 129 122 123 120 109 114 134 98 95 133 108 108 124 115 99 92 97 132 106 116 115 120 116 123 91 94 107 115 114 110 98 81 94 109 114 86 92 97 105 107 94 98 79 93 83 96 70 71 88 71样例输出 #1
69
11样例输入 #2
90 103 99 83 102 70 86 70 99 71样例输出 #2
5
3王婆卖瓜
感觉有收获或者想跟上我的进度刷题的可以点个关注或者点赞收藏评论都可以
参考来源 NOIP 1999 普及组 洛谷题目-传送门 参考材料-TernaryTree
