 /**//*
题意:给出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
搜索
最新评论

|
|