题目大意：
有N只可爱的小海龟在赛跑。询问每只小海龟它是第几名，它会回答你两个数，ai,bi，分别表示在它前面的小海龟数和在它后面的小海龟数。接着你发现其中有些小海龟对你撒了谎，因为根据他们的说法你根本没法给他们排队！但是你是善良的，你不希望有很多小海龟在撒谎，想找出最少有哪几只小海龟在撒谎。（注意：小海龟的名次可能是并列的！）
分析：
若一只海龟说了真话，那么该海龟的位置一定是在区间[ai+1,n-bi] 上。若有k只海龟选择了相同的区间 ，则根据并列关系，该区间最多能同时拥有min{n-ai-bi,k}只海龟（多出来的海龟肯定是说谎的，预先排除掉）。可以计算出每个区间最多能有多少只海龟，把数值看做区间的“权”。则问题转化为，在一些带权区间中，选出权和最大的区间，使它们之间不能互相重叠。
算法：
算出每个出现过的区间的“权”vi ，接下来的算法就是动态规划了。先按右端点坐标从小到大排序，令pi 为在区间 i左边的且与之无公共点的最大区间编号，设状态f[i] 为在前i 个区间中可选出区间的最大权和，则状态转移方程为f(i)=max(f(i-1),f(pi)+vi) ，说真话海龟的最大数量就是最后一个区间的f(i) 值。
论文：/Files/yzhw/range.rar
注意，在区间类问题中，要合理设计状态，究竟状态表示的是前i个区间（第i个区间不一定取）还是第i个区间一定要取的前i个区间。
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