Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

PKU 3636 Nested Dolls---贪心

Posted on 2009-09-09 21:34 Uriel 阅读(616) 评论(0)  编辑 收藏 引用 所属分类: POJ贪心
搞了很久的一题。。。
这题跟1065一样,还是两个月前做的,1065过了,3636一直TLE。。
原来的方法很恶心的。。要遍历很多遍知道所有的数都归类过,后来改了一下,还是TLE。。
无奈上网搜解题报告。。http://hi.baidu.com/findthegateopen/blog/item/8d7694127d16b7d8f7039eb1.html
感叹下,二分的思想真是神奇啊。。

贴下三个版本的代码。。

/*Problem: 3636  User: Gilhirith 
   Memory: N/A  Time: N/A 
   Language: C++  Result: Time Limit Exceeded
*/
 

#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>

struct In{
    
int L;
    
int W;
}
S[20010];

int i,x,sum,n,t,flag,y,z,r;

int cmp(const void *a,const void *b)
{
    
struct In *= (In *)a;
    
struct In *= (In *)b;
    
if(c->!= d->L) return c->L-d->L;
    
else return c->- d->W;
}


int main()
{
    scanf(
"%d",&t);
    
while(t--)
    
{
//        memset(S,0x00,sizeof(S));
        scanf("%d",&n);
        x
=n;
        
for(i=0;i<n;i++)
        
{
            scanf(
"%d %d",&S[i].L,&S[i].W);
        }

        sum
=0;
        qsort(S,n,
sizeof(S[0]),cmp); 
        
while(x>0)
        
{
            flag
=0;
            
for(i=0;i<n;i++)
            
{
                
if(S[i].L==0)continue;
                
else
                
{
                    
if(flag==0)
                    
{
                        sum
++;
                        x
--;
                        S[i].L
=0;
                        r
=S[i].W;
                        z
=S[i].L;
                        flag
=1;
                        
continue;
                    }

                    
else if(flag==1 && r<S[i].W && z<S[i].L)
                    
{
                        x
--;
                        z
=S[i].L;
                        S[i].L
=0;
                        r
=S[i].W;
                    }

                    
else if(flag==1)
                    
{
                        
continue;
                    }

                }

            }

        }
        
        printf(
"%d\n",sum); 
    }
            
    
return 0;
}


/*Problem: 3636  User: Gilhirith 
   Memory: N/A  Time: N/A 
   Language: C++  Result: Time Limit Exceeded
*/
 

#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<algorithm>
using namespace std;

struct In{
    
int L;
    
int W;
}
S[20010];

int t,i,j,n,sum,res[20010];

bool cmp(In a,In b)
{
    
if(a.L != b.L) return a.L > b.L;
    
else return b.W > a.W;
}


int main()
{
    scanf(
"%d",&t);
    
while(t--)
    
{
        scanf(
"%d",&n);
        
for(i=0;i<n;i++)
        
{
            scanf(
"%d %d",&S[i].L,&S[i].W);
            res[i]
=0;
        }

        sum
=0;
        sort(S,S
+n,cmp);
        
for(i=1;i<n;i++)
        
{
            
for(j=0;j<i;j++)
            
{
                
if(S[i].L<=S[j].L && S[i].W>=S[j].W)
                
{
                    
if(res[j]+1>res[i])res[i]=res[j]+1;
                }

            }

            
if(sum<res[i])sum=res[i];
        }
        
        printf(
"%d\n",sum+1); 
    }
        
//    system("PAUSE");    
    return 0;
}




/*Problem: 3636  User: Gilhirith 
   Memory: 496K  Time: 157MS 
   Language: C++  Result: Accepted
*/
 

#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<algorithm>
using namespace std;

struct In{
    
int L;
    
int W;
}
S[20010];

int t,i,j,n,sum,res[20010];

bool cmp(In a,In b)
{
    
if(a.L != b.L) return a.L < b.L;
    
else return b.W < a.W;
}


int Sov()
{
    
int T[20010],len=0,r,l,mid;
    memset(T,
0,sizeof(T));
    
for(int i=0;i<n;i++)
    
{
        l
=0;
        r
=len;
        
while(l<r)
        
{
            mid
=(l+r)/2;
            
if(T[mid]>=S[i].W)l=mid+1;
            
else
                r
=mid;
        }

        
if(len==l)len++;
        T[l]
=S[i].W;
    }

    
return len;
}


int main()
{
    scanf(
"%d",&t);
    
while(t--)
    
{
        scanf(
"%d",&n);
        
for(i=0;i<n;i++)
        
{
            scanf(
"%d %d",&S[i].L,&S[i].W);
            res[i]
=0;
        }

        sort(S,S
+n,cmp);
        printf(
"%d\n",Sov()); 
    }
            
    
return 0;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理