BZOJ2244 拦截导弹
2018-09-18 06:25:05来源:博客园 阅读 ()
此题最早看到是在我还什么都不会的去年的暑期集训,是V8讲的DP专题,我当时还跑去问这概率怎么做。这道题要求的是二维最长不上升子序列,加上位置一维就成了三维偏序问题,也就是套用CDQ分治,对位置排序,然后对一维分治,对剩下的一维树状数组,类似的问题用树状数组套平衡树也能解决,但似乎常数很大。然后这题的第一个关键就是在做CDQ的时候先做CDQ(l,mid)的区间,然后去计算左边对右边的影响,最后去计算CDQ(mid+1,r),昨晚看别人博客中说这是显然的,当时我就懵逼了,于是这题今天上课看了很久。发现的确要这么做的,因为其实你是在维护第三维树状数组的时候去做了这个DP的过程,当计算以该点为结尾的最长不上升子序列时,你当然应该先做左区间,然后就可以去更新一下相对右边这些点的值,然后就再去做CDQ的右区间。具体是分别维护区间的最长不上升子序列的长度,以及出现的次数。做法是这样的,首先对左右两边分别按照第二维从小到大排序,将左边的所有的第二维大于右边的点全部加入树状数组,更新第三维,要注意更新和查询的方向正好是反过来的,因为你要查的是大于右边某个值的最长不上升子序列的长度,然后更新一下dp数组,也就是代码中的f[0]数组。然后再把整个序列反过来做一遍CDQ,求以某个点为开始的最长不上升子序列。
加一个学习的链接:https://www.cnblogs.com/liu-runda/p/6416195.html
#include<bits/stdc++.h> #define ll long double #define pb push_back #define _mp make_pair const int maxn=1e5+7; const int mod=1e9+7; using namespace std; int n; int h[2][maxn],v[2][maxn]; int iq[maxn],hq[maxn],vq[maxn]; int f[2][maxn]; ll g[2][maxn]; int MAX[maxn]; ll CNT[maxn]; void add1(int x,int w,ll cnt) { while(x>0) { if(MAX[x]<w) { MAX[x]=w;CNT[x]=cnt; } else if(MAX[x]==w)CNT[x]+=cnt; x-=x&-x; } } void add2(int x,int w,ll cnt) { while(x<maxn) { if(MAX[x]<w) { MAX[x]=w;CNT[x]=cnt; } else if(MAX[x]==w)CNT[x]+=cnt; x+=x&-x; } } int query1(int x) { int ans=0; while(x<maxn) { if(MAX[x]>ans)ans=MAX[x]; x+=x&-x; } return ans; } int query2(int x) { int ans=0; while(x>0) { if(MAX[x]>ans)ans=MAX[x]; x-=x&-x; } return ans; } ll query_cnt(int x,int val) { ll ans=0; while(x<maxn) { if(MAX[x]==val)ans+=CNT[x]; x+=x&-x; } return ans; } ll query_cnt2(int x,int val) { ll ans=0; while(x>0) { if(MAX[x]==val)ans+=CNT[x]; x-=x&-x; } return ans; } bool cmp1(const int& a,const int& b) { return h[0][a]<h[0][b]; } bool cmp2(const int& a,const int& b) { return v[0][a]<v[0][b]; } bool cmp3(const int& a,const int& b) { return h[1][a]<h[1][b]; } void del1(int x) { while(x>0) { MAX[x]=CNT[x]=0; x-=x&-x; } } void del2(int x) { while(x<maxn) { MAX[x]=CNT[x]=0; x+=x&-x; } } void cdq1(int l,int r) { if(l==r)return; int mid=(l+r)>>1; cdq1(l,mid); for(int i=l;i<=r;i++)iq[i]=i; sort(iq+l,iq+mid+1,cmp1); sort(iq+mid+1,iq+r+1,cmp1); int pp=mid; for(int i=r;i>mid;i--) { while(pp>=l&&h[0][iq[pp]]>=h[0][iq[i]]) { add1(v[0][iq[pp]],f[0][iq[pp]],g[0][iq[pp]]); pp--; } int tmp=query1(v[0][iq[i]]); if(tmp+1>f[0][iq[i]]) { f[0][iq[i]]=tmp+1;g[0][iq[i]]=query_cnt(v[0][iq[i]],tmp); } else if(tmp+1==f[0][iq[i]]) { g[0][iq[i]]+=query_cnt(v[0][iq[i]],tmp); } } for(int i=mid;i>pp;i--) { del1(v[0][iq[i]]); } cdq1(mid+1,r); } void cdq2(int l,int r) { if(l==r)return; int mid=(l+r)>>1; cdq2(l,mid); for(int i=l;i<=r;i++)iq[i]=i; sort(iq+l,iq+mid+1,cmp3); sort(iq+mid+1,iq+r+1,cmp3); int pp=l; for(int i=mid+1;i<=r;i++) { while(pp<=mid&&h[1][iq[pp]]<=h[1][iq[i]]) { add2(v[1][iq[pp]],f[1][iq[pp]],g[1][iq[pp]]); pp++; } int tmp=query2(v[1][iq[i]]); if(tmp+1>f[1][iq[i]]) { f[1][iq[i]]=tmp+1;g[1][iq[i]]=query_cnt2(v[1][iq[i]],tmp); } else if(tmp+1==f[1][iq[i]]) { g[1][iq[i]]+=query_cnt2(v[1][iq[i]],tmp); } } for(int i=l;i<pp;i++) { del2(v[1][iq[i]]); } cdq2(mid+1,r); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&h[0][i],&v[0][i]); iq[i]=i; } // cout<<222<<endl; sort(iq+1,iq+1+n,cmp1); int tot=0,las=-1; for(int i=1;i<=n;i++) { if(las!=h[0][iq[i]]) { las=h[0][iq[i]]; ++tot; } h[0][iq[i]]=tot; } tot=0;las=-1; for(int i=1;i<=n;i++) iq[i]=i; sort(iq+1,iq+1+n,cmp2); for(int i=1;i<=n;i++) { if(las!=v[0][iq[i]]) { las=v[0][iq[i]]; ++tot; }v[0][iq[i]]=tot; } for(int i=1;i<=n;i++) { h[1][i]=h[0][n+1-i]; v[1][i]=v[0][n+1-i]; } for(int i=1;i<=n;i++) { iq[i]=i; f[0][i]=f[1][i]=g[0][i]=g[1][i]=1; } // cout<<222<<endl; cdq1(1,n);cdq2(1,n); // cout<<222<<endl; int ans=0; for(int i=1;i<=n;i++) { if(f[0][i]>ans)ans=f[0][i]; } printf("%d\n",ans); ll sum=0; for(int i=1;i<=n;i++) { if(f[0][i]==ans)sum+=g[0][i]; } //cout<<sum<<endl; for(int i=1;i<=n;i++) { // cout<<g[0][i]<<" "<<g[1][n-i+1]<<endl; if(f[0][i]+f[1][n-i+1]!=ans+1)printf("%.8f ",0.0); else printf("%.8f ",double(g[0][i]*g[1][n-i+1]/(sum))); //cout<<endl; // cout<<222<<endl; } // } // for(int i=1;i<=n;i++) cout<<g[0][i]<<" "<<g[1][n-i+1]<<endl; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:POJ3252Round Numbers(数位dp)
下一篇:平衡 balance
- 算法训练 拦截导弹(最长递增子序列和最长递减子序列问题, 2020-02-20
- 题解-洛谷P1020P导弹拦截(求单调序列长度的优化) 2019-02-20
- 百练_2945 拦截导弹(DP) 2018-06-17
- 动态规划 导弹拦截 2018-06-17
- 1044 拦截导弹 1999年NOIP全国联赛提高组 个人博客:attac 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash