> 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方程是什么？我的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