/**//* 题意:给出2*N的序列,每个数∈[1,N]出现2次 2个数之间的间隔为得分, 求得一个得分后会删除这两个数,问最大得分
N比较大,应该是贪心 从后往前删除数,用树状数组求得sum(x)个数 对于嵌套的、相互独立的,先删除谁都没关系 但对于包含关系的,必须先删除外围的,所以从后开始(从前开始也一样) */ #include<cstdio> #include<cstring> const int MAXN = 200005; int c[MAXN],seq[MAXN]; int beg[MAXN],end[MAXN]; int N; int lowbit(int x){return x&(-x);} void update(int p,int x) { while(p<=N) { c[p]+=x; p+=lowbit(p); } } int sum(int p) { int ans = 0; while(p>0) { ans+=c[p]; p-=lowbit(p); } return ans; } int main() { while(~scanf("%d",&N)) { N*=2; int x; for(int i=1;i<=N;i++) { scanf("%d",&seq[i]); if(beg[seq[i]])end[seq[i]]=i; else beg[seq[i]]=i; update(i,1); } int ans = 0; for(int i=N;i;i--) { if(beg[seq[i]]==0)continue; ans+=sum(i)-sum(beg[seq[i]]); update(beg[seq[i]],-1); update(i,-1); beg[seq[i]] = 0; } printf("%d\n",ans); } return 0; }
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|