• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 閱讀(622) 評論(0)  編輯 收藏 引用 所屬分類: POJ貪心
            搞了很久的一題。。。
            這題跟1065一樣,還是兩個月前做的,1065過了,3636一直TLE。。
            原來的方法很惡心的。。要遍歷很多遍知道所有的數(shù)都歸類過,后來改了一下,還是TLE。。
            無奈上網(wǎng)搜解題報告。。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;
            }
            亚洲精品蜜桃久久久久久| 久久久这里有精品中文字幕| 久久九色综合九色99伊人| 蜜桃麻豆www久久| 久久国产精品成人免费 | 99久久国产综合精品麻豆| 99久久这里只精品国产免费| 久久久久免费视频| 久久婷婷五月综合色99啪ak| 久久亚洲精品无码播放| 无码任你躁久久久久久| 欧美日韩精品久久久久| 亚洲国产精品18久久久久久| 久久99精品久久久久婷婷| 久久久久亚洲AV无码专区首JN | 久久综合狠狠综合久久综合88| 亚洲欧美精品一区久久中文字幕| 性做久久久久久免费观看| 亚洲精品无码久久一线| 99久久99久久| 久久久久人妻一区精品| 欧美黑人激情性久久| 人妻精品久久久久中文字幕69| 精品综合久久久久久97超人| 国产精品熟女福利久久AV| 久久精品亚洲男人的天堂| 亚洲va中文字幕无码久久| 亚洲一本综合久久| 久久久久人妻一区精品| 久久香蕉国产线看观看精品yw| 久久这里只精品国产99热| 久久亚洲精品无码aⅴ大香| a级成人毛片久久| 亚洲精品乱码久久久久久蜜桃| 九九精品99久久久香蕉| 亚洲欧美成人久久综合中文网| 国产亚洲精品美女久久久| 久久精品免费全国观看国产| 免费国产99久久久香蕉| 婷婷久久久亚洲欧洲日产国码AV | 国产精品99久久久久久www|