网站注册怎么注销,网站开发会遇到的问题,做网站需要了解,电子商务网站建设 课件P1020 导弹拦截 の 题目传送门。
解题思路
显然#xff0c;第一问求的是最长不上升子序列。
于是接下来直接抛开第一问不谈#xff0c;也不考虑优化#xff0c;直接考虑第二问。待会就知道原因了。
引理#xff1a;Dilworth 定理 狄尔沃斯定理亦称偏序集分解定理#…P1020 导弹拦截 の 题目传送门。
解题思路
显然第一问求的是最长不上升子序列。
于是接下来直接抛开第一问不谈也不考虑优化直接考虑第二问。待会就知道原因了。
引理Dilworth 定理 狄尔沃斯定理亦称偏序集分解定理该定理断言对于任意有限偏序集其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真它断言对于任意有限偏序集其最长链中元素的数目必等于其最小反链划分中反链的数目。 该定理在该问题上可以理解成把序列分成不上升子序列的最少个数等于序列的最长上升子序列长度。把序列分成不降子序列的最少个数等于序列的最长下降子序列长度。
则第二问等价于最长上升子序列。
贪心
先不管引理对我们有什么用我们直接思考第二问贪心怎么做。
对于每个数既可以把它接到已有的导弹拦截后面也可以建立一个新系统。要使子序列数最少应尽量不建立新序列。
另外应让每个导弹系统的末尾尽可能大这样能接的数更多。因为一个数若能接到小数后面必然能接到大数后面反之则不成立。根据这些想法可总结出如下贪心流程
从前往后扫描每个数对于当前数
1.若现有子序列的结尾都小于它则创建新子序列。
2.否则将它放到结尾大于等于它的最小数后
贪心证明
我们可以知道证明 AB可证 A≤B 且 A≥B。
记 A 为贪心解B 为最优解。
贪心解能覆盖所有数且形成的都是不升序列因此合法。由定义B≤A。
假设最优解对应的方案和贪心方案不同从前往后找到第一个不在同一序列的数 x。假设贪心解中 x 前面的数是 a最优解中 x 前面的数是 ba 后面的数是 y由于贪心会让当前数接到大于等于它的最小数后面所以 ,x,y≤a≤b。 此时在最优解中把 x 一直到序列末尾和 y 一直到序列末尾交换位置这样做不影响正确性也不增加序列个数但会使 x 在最优解和贪心解中所处的位置相同。由于序列中的数是有限的只要一直做下去一定能使最优解变为贪心解。因此A≤B。
等等第二问根据引理是求最长上升子序列但是贪心也可以求。说明我们的贪心解法等于最长上升子序列 引理作用即在此处
贪心可以求上升子序列自然连第一问求的最长不上升子序列也可以求了。
最坏复杂度O(n2)但是数据很水可以完美通过此题。
我们也可以对此代码进行二分优化即查找 k 的时候
AC 代码
#includebits/stdc.h
#define up(l,r,i) for(int il,END##ir;iEND##i;i)
#define dn(r,l,i) for(int ir,END##il;iEND##i;--i)
using namespace std;
typedef long long i64;
const int INF 2147483647;
const int MAXN1e53;
int n,t,H[MAXN],F[MAXN];
int main(){while(~scanf(%d,H[n])); --n;t0,memset(F,0,sizeof(F)),F[0]INF;up(1,n,i){int l0,rt1; while(r-l1){int ml(r-l)/2;if(F[m]H[i]) lm; else rm;}int xl1; // dp[i]if(xt) tx; F[x]H[i];}printf(%d\n,t);t0,memset(F,0,sizeof(F)),F[0]0;up(1,n,i){int l0,rt1; while(r-l1){int ml(r-l)/2;if(F[m]H[i]) lm; else rm;}int xl1;if(xt) tx; F[x]H[i];}printf(%d\n,t);return 0;
}
