锐客网

  1. 首页 > it技术 > >

P1020|P1020 导弹拦截 dp 树状数组维护最长升序列

题目描述 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
【P1020|P1020 导弹拦截 dp 树状数组维护最长升序列】输入导弹依次飞来的高度（雷达给出的高度数据是\le 50000≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入输出格式 输入格式：

11行，若干个整数（个数\le 100000≤100000）

输出格式：

22行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例 输入样例#1：复制

389 207 155 300 299 170 158 65

输出样例#1：复制
6 2


一开始想以 前i个和当前高度这两个为dp转移量dp不出来。。

第一问：求最大不上升子序列长度（小于等于）
第二问：求最大 上升子序列（严格大于）


有一半数据为nlogn的写的就过了一半数据

P1020|P1020 导弹拦截 dp 树状数组维护最长升序列
文章图片
P1020|P1020 导弹拦截 dp 树状数组维护最长升序列
文章图片
#include using namespace std; //input #define rep(i,x,y) for(int i=(x); i<=(y); ++i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m); #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s) #define LL long long #define REP(i,N)for(int i=0; i<(N); i++) #define CLR(A,v)memset(A,v,sizeof A) // #define N 65 #define inf -0x3f3f3f3f int dp[100001]; int dp2[100001]; int a[100005]; int main() { int x; int cnt=0; while(RI(x)==1)a[++cnt]=x; rep(i,1,cnt) { dp[i]=1; dp2[i]=1; } int maxx=0; int minn=0; rep(i,2,cnt) { for(int j=1; j=a[i])dp[i]=max(dp[i],dp[j]+1); maxx=max(dp[i],maxx); if(a[j]1); minn=max(dp2[i],minn); } } cout<
View Code
另一种非常非常巧妙的方法：
P1020|P1020 导弹拦截 dp 树状数组维护最长升序列
文章图片
P1020|P1020 导弹拦截 dp 树状数组维护最长升序列
文章图片
直接维护一个非升序列和一个非降序列，维护的过程就能用上面两个神奇的STL（当然非升序列的upper_bound()要重载cmp）。不多说，上代码#include using namespace std; int a[100005],f[100005],l[100005]; struct cmp{bool operator()(int a,int b){return a>b; }}; int main() { int n=1; while(cin>>a[n])n++; n--; int con=1,cont=1; l[1]=f[1]=a[1]; for(int i=2; i<=n; i++) { if(l[cont]>=a[i])l[++cont]=a[i]; else l[upper_bound(l+1,l+cont+1,a[i],cmp())-l]=a[i]; if(f[con]a[i]; else f[lower_bound(f+1,f+con+1,a[i])-f]=a[i]; } cout<
View Code

树状数组：
P1020|P1020 导弹拦截 dp 树状数组维护最长升序列
文章图片
P1020|P1020 导弹拦截 dp 树状数组维护最长升序列
文章图片
#include using namespace std; //input #define rep(i,x,y) for(int i=(x); i<=(y); ++i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m); #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s) #define LL long long #define REP(i,N)for(int i=0; i<(N); i++) #define CLR(A,v)memset(A,v,sizeof A) // #define N 100005 #define inf -0x3f3f3f3fint c[N]; int lowbit(int x) { return x&(-x); }void update(int x,int v) { for(int i=x; i<=N; i+=lowbit(i)) c[i]=max(c[i],v); } int sum(int x) { int ans=0; for(int i=x; i>0; i-=lowbit(i)) ans=max(ans,c[i]); return ans; }int a[N]; int main() { int x; int cnt=0; while(RI(x)==1)a[++cnt]=x; int ans1=0,ans2=0; for(int i=cnt; i>=1; i--) { int p=sum(a[i])+1; update( a[i],p); ans1=max(ans1,p); } cout
View Code

这里维护的是最大值

类似之前有一题母牛耳聋的问题
那里维护的是1 意为存在一个牛那题可以方便的求出在这头牛前面有几头牛（这里要是维护1是错的。。）
树状数组的用法非常灵活！！！！











转载于:https://www.cnblogs.com/bxd123/p/10507468.html

    推荐阅读


    上一篇：Logback|Logback 整合 RabbitMQ 实现统一日志输出

    下一篇：ubuntu16.04的下载安装