#include<iostream.h>
#include<stdlib.h>
typedef struct lll
  {
  long long x,y;
  }Line;
Line a[1000];
long long n;
long long map[1000][1000];
int cmp(const void*a,const void*b)
{
  Line aa,bb;
  aa=*(Line*)a;
  bb=*(Line*)b;
  if(aa.y!=bb.y) {
        if(aa.y>bb.y) return 1;
        else return -1;
         }    
  else {
      if(aa.x>bb.x) return 1;
      else if(aa.x==bb.x) return 0;
      else return -1;
      }      
}

long long dfs(long long ii,long long now)//从下标ii->n中去now个不相交的线段方案数
{
   long long tp,i,j;   
   if(now==1) return n-ii; 
   if(map[ii][now]!=-1l)
      return map[ii][now];
   tp=0;
   for(i=ii;i<n-now;i++)
      {
        for(j=i+1;j<n-now+1;j++)
           if(a[j].x>=a[i].y) 
              break;
        if(j<n)
             tp+=dfs(j,now-1);
      }
  map[ii][now]=tp;     
  return tp;
}                       
 

main()
{
  long long i,j,edg,k;
  while(cin>>n)
  {
    for(i=0;i<n;i++)
      { 
        cin>>a[i].x>>a[i].y;
        if(a[i].x>a[i].y)//x存首端点..y存尾端点..
        {
           k=a[i].x;
           a[i].x=a[i].y;
           a[i].y=k;
        }
      }                   
    for(i=0;i<=n;i++)
        for(j=0;j<=n;j++)
            map[i][j]=-1l;
    qsort(a,n,sizeof(a[0]),cmp);  //按y排序
    edg=a[0].y;  //贪心求最大可剩余的线段数
    k=1; 
    for(i=1;i<n;i++)
      if(a[i].x>=edg)
        {
         k++;
         edg=a[i].y;
        }  
    j=dfs(0,k);  //选取不相交的k个线段方案数..对应擦除n-k条直线方案数
    cout<<n-k<<" "<<j<<endl;
   }
}    
  

• Re:wa的不行了....达人指点一下...那里错了 (21) wavemoon 2005-08-28 19:34:40
  • Re:wa的不行了....达人指点一下...那里错了 (35) s_1 2005-09-01 02:27:39
• Re:wa的不行了....达人指点一下...那里错了 (1737) s_1 2005-09-01 17:29:17
  • 无语。。。 (43) 10101101 2005-09-01 18:22:07
  • 谁说了线段一定是从左到右画的？ (0) achilles 2005-09-02 12:48:07
    • 恩...这就是理解德问题了,一般先给出的就是左边德,后给出德都是右边的,可是总是有很多类似德E心题,比如告诉给出你XY坐标,但是先给德是Y坐标,后给的是X坐标而且INPUT没说示例离还没反映出来之累的 (0) uni 2005-09-02 15:49:51
    • 这种违反约定俗成而且还没说的东西,得看经验,而且,就算有经验,别人要是在这方面想好好德E心你,你肯定没辙 (0) uni 2005-09-02 15:50:55