预处理所有包含关系，记忆化搜索。
1 #include <iostream>
2 using namespace std;
3 int n;
4 int pos[600][2];
5 int link[600][600];
6 int dp[600];
7 int pre[600];
8 bool contain(int a,int b){
9 if (pos[a][0]<pos[b][0]&&pos[a][1]>pos[b][1]) return true;
10 else return false;
11 }
12
13 int calc(int x){
14 if (dp[x]==0){
15 int mm=0,mpos=0;
16 for (int i=1;i<=link[x][0];++i) if (calc(link[x][i])>mm){
17 mm=calc(link[x][i]);
18 mpos=link[x][i];
19 }
20 dp[x]=mm+1;
21 pre[x]=mpos;
22 }
23 return dp[x];
24 }
25
26 int main(){
27 scanf("%d",&n);
28 for (int i=1;i<=n;++i) scanf("%d %d",&pos[i][0],&pos[i][1]);
29 for (int i=1;i<=n;++i) if (pos[i][0]>pos[i][1]){
30 int m=pos[i][0];
31 pos[i][0]=pos[i][1];
32 pos[i][1]=m;
33 }
34 for (int i=1;i<=n;++i)
35 for (int j=1;j<=n;++j) if (j!=i&&contain(j,i)){
36 link[i][++link[i][0]]=j;
37 }
38 int ans=0,apos=0;
39 for (int i=1;i<=n;++i) if (calc(i)>ans){
40 ans=calc(i);
41 apos=i;
42 }
43 cout<<ans<<endl;
44 int x=apos;
45 while (x>0){
46 printf("%d ",x);
47 x=pre[x];
48 }
49 }
50
posted on 2008-11-12 11:50
Joseph 阅读(257)
评论(0) 编辑 收藏 引用