題目大意：
有N只可愛(ài)的小海龜在賽跑。詢問(wèn)每只小海龜它是第幾名，它會(huì)回答你兩個(gè)數(shù)，ai,bi，分別表示在它前面的小海龜數(shù)和在它后面的小海龜數(shù)。接著你發(fā)現(xiàn)其中有些小海龜對(duì)你撒了謊，因?yàn)楦鶕?jù)他們的說(shuō)法你根本沒(méi)法給他們排隊(duì)！但是你是善良的，你不希望有很多小海龜在撒謊，想找出最少有哪幾只小海龜在撒謊。（注意：小海龜?shù)拿慰赡苁遣⒘械模。?/span>
分析：
若一只海龜說(shuō)了真話，那么該海龜?shù)奈恢靡欢ㄊ窃趨^(qū)間[ai+1,n-bi] 上。若有k只海龜選擇了相同的區(qū)間 ，則根據(jù)并列關(guān)系，該區(qū)間最多能同時(shí)擁有min{n-ai-bi,k}只海龜（多出來(lái)的海龜肯定是說(shuō)謊的，預(yù)先排除掉）?？梢杂?jì)算出每個(gè)區(qū)間最多能有多少只海龜，把數(shù)值看做區(qū)間的“權(quán)”。則問(wèn)題轉(zhuǎn)化為，在一些帶權(quán)區(qū)間中，選出權(quán)和最大的區(qū)間，使它們之間不能互相重疊。
算法：
算出每個(gè)出現(xiàn)過(guò)的區(qū)間的“權(quán)”vi ，接下來(lái)的算法就是動(dòng)態(tài)規(guī)劃了。先按右端點(diǎn)坐標(biāo)從小到大排序，令pi 為在區(qū)間 i左邊的且與之無(wú)公共點(diǎn)的最大區(qū)間編號(hào)，設(shè)狀態(tài)f[i] 為在前i 個(gè)區(qū)間中可選出區(qū)間的最大權(quán)和，則狀態(tài)轉(zhuǎn)移方程為f(i)=max(f(i-1),f(pi)+vi) ，說(shuō)真話海龜?shù)淖畲髷?shù)量就是最后一個(gè)區(qū)間的f(i) 值。
論文：/Files/yzhw/range.rar
注意，在區(qū)間類(lèi)問(wèn)題中，要合理設(shè)計(jì)狀態(tài)，究竟?fàn)顟B(tài)表示的是前i個(gè)區(qū)間（第i個(gè)區(qū)間不一定?。┻€是第i個(gè)區(qū)間一定要取的前i個(gè)區(qū)間。
1
# include <iostream>
2# include <map>
3# include <vector>
4# include <cstring>
5# include <cstdio>
6using namespace std;
7vector<int> ans;
8map<int,vector<int> > refer;
9# define pos(a,b) (((b)<<10)|(a))
10struct node
11
{
12
int s,e,val,per;
13
}ran[1001];
14int dp[1001];
15int path[1001];
16bool used[1001];
17int c=1;
18int searchper(int pos)
19{
20 int s=1,mid,e=c;
21 e--;
22 while(s<=e)
23
{
24 mid=(s+e)/2;
25 if(ran[mid].e>=pos)
26 e=mid-1;
27 else
28 s=mid+1;
29
}
30 return e;
31}
32int main()
33{
34 int n;
35 scanf("%d",&n);
36 for(int i=0;i<n;i++)
37 {
38 int a,b;
39 scanf("%d%d",&a,&b);
40 if(a+b+1>n)
41 ans.push_back(i);
42 else
43 {
44 if(refer[pos(a+1,n-b)].size()<n-b-a)
45 refer[pos(a+1,n-b)].push_back(i);
46 else
47 ans.push_back(i);
48 }
49 }
50 for(map<int,vector<int> >::iterator i=refer.begin();i!=refer.end();i++)
51 {
52 ran[c].s=(i->first)&1023;
53 ran[c].e=((i->first)>>10);
54 ran[c++].val=(i->second).size();
55 }
56 for(int i=1;i<c;i++)
57 ran[i].per=searchper(ran[i].s);
58 dp[0]=0;
59 path[0]=-1;
60 for(int i=1;i<c;i++)
61 {
62 if(dp[i-1]>dp[ran[i].per]+ran[i].val)
63 path[i]=0,dp[i]=dp[i-1];
64 else
65 path[i]=1,dp[i]=dp[ran[i].per]+ran[i].val;
66 }
67 memset(used,false,sizeof(used));
68 int p=c-1;
69 while(p)
70 {
71 if(path[p])
72 {
73 used[p]=true;
74 p=ran[p].per;
75 }
76 else
77 p--;
78 }
79 for(int i=1;i<c;i++)
80 if(!used[i])
81 for(int j=0;j<refer[pos(ran[i].s,ran[i].e)].size();j++)
82 ans.push_back(refer[pos(ran[i].s,ran[i].e)][j]);
83 printf("%d",ans.size());
84 for(int i=0;i<ans.size();i++)
85 printf(" %d",ans[i]+1);
86 printf("\n");
87 return 0;
88}
89
90