旅游网站内容,网站集约化建设情况,安阳seo关键词优化,上海人才市场招聘拦截导弹 (missile.pas/c/cpp) 来源#xff1a;NOIP1999(提高组) 第一题 【问题描述】 某国为了防御敌国的导弹袭击#xff0c;发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷#xff1a;虽然它的第一发炮弹能够到达任意的高度#xff0c;但是以后每一发炮弹都不…拦截导弹 (missile.pas/c/cpp) 来源NOIP1999(提高组) 第一题 【问题描述】 某国为了防御敌国的导弹袭击发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷虽然它的第一发炮弹能够到达任意的高度但是以后每一发炮弹都不能高于前一发的高度。某天雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段所以只有一套系统因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度雷达给出的高度数据是不大于30000的正整数计算这套系统最多能拦截多少导弹如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 【输入文件】missile.in 单独一行列出导弹依次飞来的高度。 【输出文件】missile.out 两行分别是最多能拦截的导弹数要拦截所有导弹最少要配备的系统数 【输入样例】 389 207 155 300 299 170 158 65 【输出样例】 6 2 【问题分析】 有经验的选手不难看出这是一个求最长非升子序列问题显然标准算法是动态规划。 以导弹依次飞来的顺序为阶段设计状态opt[i]表示前i个导弹中拦截了导弹i可以拦截最多能拦截到的导弹的个数。 状态转移方程 opt[i]max(opt[j])1 (h[i]h[j],0ji) {h[i]存第i个导弹的高度} 最大的opt[i]就是最终的解。 这只解决了第一问对于第二问最直观的方法就是求完一次opt[i]后把刚才要打的导弹去掉在求一次opt[i]直到打完所有的导弹但这样做就错了。 不难举出反例 6 1 7 3 2 错解 6 3 2/1/7 正解6 1/7 3 2 其实认真分析一下题就回发现每一个导弹最终的结果都是要被打的如果它后面有一个比它高的导弹那打它的这个装置无论如何也不能打那个导弹了经过这么一分析这个问题便抽象成在已知序列里找最长上升序列的问题。 求最长上升序列和上面说的求最长非升序列是一样的这里就不多说了。 复杂度时间复杂度为ON2空间复杂度为ON。 题意一种导弹拦截系统的第一发炮弹能够到达任意的高度但是以后每一发炮弹都不能高于前一发的高度。某天雷达捕捉 到敌国的导弹来袭。由于该系统还在试用阶段所以只有一套系统因此有可能不能拦截所有的导弹。输入导弹依次飞来的高 度计算这套系统最多能拦截多少导弹如果要拦截所有导弹最少要配备多少套这种导弹拦截系统 分析 第一问很简单就是求最长不上升子序列。对于第二问不能用贪心的方法来做因为有反例7 5 4 1 6 3 2. 我们把第二问的问题抽象出来那就是把一个数列划分成最少的最长不升子序列这里我们要介绍一个很优美的定理。 Dilworth定理对于一个偏序集最少链划分等于最长反链长度。 Dilworth定理的对偶定理对于一个偏序集其最少反链划分数等于其最长链的长度。 也就是说把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度。 下面来说说这个定理是怎么来的 偏序集的定义偏序是在集合X上的二元关系≤这只是个抽象符号不是“小于或等于”它满足自反性、反对称性和传递 性。即对于X中的任意元素a,b和c有: (1)自反性a≤a; (2)反对称性如果a≤b且b≤a则有ab; (3)传递性如果a≤b且b≤c则a≤c 。 带有偏序关系的集合称为偏序集。 令(X,≤)是一个偏序集对于集合中的两个元素a、b如果有a≤b或者b≤a则称a和b是可比的否则a和b不可比。 在这个例子(反链)中元素RiRj是指(ij) and (aiaj) 一个反链A是X的一个子集它的任意两个元素都不能进行比较。 一个链C是X的一个子集它的任意两个元素都可比。 【定理】 在X中对于元素a如果任意元素b都有a≤b则称a为极小元。 定理1令X,≤是一个有限偏序集并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。 其对偶定理称为Dilworth定理 令X,≤是一个有限偏序集并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。 虽然这两个定理内容相似但第一个定理证明要简单一些。此处就只证明定理1。 证明设p为最少反链个数 (1)先证明X不能划分成小于r个反链。由于r是最大链C的大小C中任两个元素都可比因此C中任两个元素都不能属于同一反 链。所以pr。 (2)设X1XA1是X1中的极小元的集合。从X1中删除A1得到X2。注意到对于X2中任意元素a2必存在X1中的元素a1使得 a1a2。令A2是X2中极小元的集合从X2中删除A2得到X3……最终会有一个Xk非空而Xk1为空。于是A1,A2,…,Ak就是X的 反链的划分同时存在链a1a2…ak其中ai在Ai内。由于r是最长链大小因此rk。由于X被划分成了k个反链因此 rkp。 (3)因此rp定理1得证。 【解决】 要求最少的覆盖按照Dilworth定理 最少链划分 最长反链长度 所以最少系统 最长导弹高度上升序列长度。 1 #includebits/stdc.h2 3 int arr[1000010];4 int dp[1000010];5 6 int main(){7 int n;8 while(~scanf(%d, n)){9 for(int i 0; i n; i) scanf(%d, arr[i]);
10
11 for(int i 0; i n; i) dp[i] 1;
12 for(int i 1; i n; i){
13 for(int j 0; j i; j){
14 if(arr[i] arr[j] dp[j]1 dp[i]) dp[i] dp[j]1;
15 }
16 }
17 int ans 0;
18 for(int i 0; i n; i) if(ans dp[i]) ans dp[i];
19 printf(%d\n, ans);
20
21 for(int i 0; i n; i) dp[i] 1;
22 for(int i 1; i n; i){
23 for(int j 0; j i; j){
24 if(arr[i] arr[j] dp[j]1 dp[i]) dp[i] dp[j]1;
25 }
26 }
27 ans 0;
28 for(int i 0; i n; i) if(ans dp[i]) ans dp[i];
29 printf(%d\n, ans);
30 }
31
32 return 0;
33 } 转载于:https://www.cnblogs.com/miaowTracy/p/5927744.html
