无聊啊,竟然把S和E还要颠倒地给出.无聊
竟然要在这个地方卡人~~~~~
> #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;
>    }
> }    
>   

• 无语。。。 (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