code如下:

  #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];
long long temp[100][100];
long long tp[100][100];
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;
      }      
}
                   
  
main()
{
  long long i,j,edg,k,tl,ff,t,ii;
  while(cin>>n)
  {
    for(i=0;i<n;i++)
      { 
        cin>>a[i].x>>a[i].y;
        if(a[i].x>a[i].y) 
           a[i].x^=a[i].y^=a[i].x^=a[i].y; 
      }     
    qsort(a,n,sizeof(a[0]),cmp);   
    edg=a[0].x; 
    k=0; 
    for(i=0;i<n;i++)
      if(a[i].x>=edg)
        {
         k++;
         edg=a[i].y;
        } 
          
   for(i=0;i<n;i++)
      for(j=0;j<n;j++)
         {
          if(a[j].x>=a[i].y)   temp[i][j]=map[i][j]=1;
          else temp[i][j]=map[i][j]=0;
         }   
   for(ff=0;ff<k-2;ff++)//A^(k-1)
     {
      for(i=0;i<n;i++)
         for(j=0;j<n;j++)
         {
           t=0;
           for(ii=0;ii<n;ii++) t+=temp[i][ii]*map[ii][j];
           tp[i][j]=t;
         }
      for(i=0;i<n;i++)
        for(j=0;j<n;j++)
           temp[i][j]=tp[i][j];
     }    
    tl=0;                      
    for(i=0;i<n;i++) 
        for(j=0;j<n;j++) 
             tl+=temp[i][j]; 

    if(k==1) tl=n;           
    cout<<n-k<<" "<<tl<<endl;
   }
}    
  

• 直接dp比较好，复杂度低，报告所用的方法比较新颖，但是复杂度实际上比较高 (1807) achilles 2005-08-29 10:37:52
  • DP方程是什么？我的O(n) (0) faintzw 2005-08-30 21:19:13
    • 前n根去掉m根的方法数。O(n^2)。你的快，不过写起来应该麻烦一些吧！ (0) zhucheng 2005-08-30 21:25:34
      • 递推表达式是怎样的 (0) egmna 2005-09-27 13:09:42