 /**//*
題意:給出2*N的序列,每個(gè)數(shù)∈[1,N]出現(xiàn)2次 2個(gè)數(shù)之間的間隔為得分,
求得一個(gè)得分后會(huì)刪除這兩個(gè)數(shù),問(wèn)最大得分

N比較大,應(yīng)該是貪心
從后往前刪除數(shù),用樹(shù)狀數(shù)組求得sum(x)個(gè)數(shù)
對(duì)于嵌套的、相互獨(dú)立的,先刪除誰(shuí)都沒(méi)關(guān)系
但對(duì)于包含關(guān)系的,必須先刪除外圍的,所以從后開(kāi)始(從前開(kāi)始也一樣)
*/
#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
搜索
最新評(píng)論

|
|