• <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>

            ACM PKU 1887 Testing the CATCHER 最長下降(上升)子序列 一維動態規劃

            http://acm.pku.edu.cn/JudgeOnline/problem?id=1887
            題目太羅嗦了,簡單的說就是求最長下降子序列;
            這是一通用題,還有最長上升子序列,都是一樣的解法.
            狀態轉移方程:
            Max(1)=1;
            Max( i )=Max{ Max(j):  1<=j<i && a[i]<a[j]   }+1;
            二十分鐘AC,下面是源代碼

            Source Code

            Problem: 
            1887  User: lnmm 
            Memory: 372K  Time: 78MS 
            Language: C
            ++  Result: Accepted 

            Source Code 
            #include
            "stdio.h"
            void main()
            {
                
            int i,j,tempMax;
                
            int nCase=1;
                
            int a[32767];
                
            int totalMax[32767];
                
            int temp;
                
            while(scanf("%d",&temp))
                
            {
                    
            if(temp==-1)break;
                    a[
            1]=temp;
                    totalMax[
            1]=1;
                    
            for(i=1;;)
                    
            {
                        scanf(
            "%d",&temp);
                        
            if(temp==-1)break;
                        
            else
                        
            {
                            a[
            ++i]=temp;
                            tempMax
            =0;             //找到i之前 的totalMax[j]最大且a[j]>a[i]的j值
                            for(j=1;j<i;j++)
                                
            if(a[i]<a[j]&&tempMax<totalMax[j])tempMax=totalMax[j];
                            totalMax[i]
            =tempMax+1;   //i取的是上面得到的值,加上本身(因為有a[j]>a[i]),所以+1
                        }

                    }

                    temp
            =0;
                    
            for(j=1;j<=i;j++)
                        
            if(totalMax[j]>temp)temp=totalMax[j];
                    printf(
            "Test #%d:\n",nCase++);
                    printf(
            "  maximum possible interceptions: %d\n\n",temp);



                }

            }

            posted on 2007-11-14 17:38 流牛ζ木馬 閱讀(2065) 評論(4)  編輯 收藏 引用

            評論

            # re: ACM PKU 1887 Testing the CATCHER 最長下降(上升)子序列 一維動態規劃 2008-10-16 16:09 大幅度

            誰有比這跟快的算法沒
            比如添加二分排序  回復  更多評論   

            # re: ACM PKU 1887 Testing the CATCHER 最長下降(上升)子序列 一維動態規劃 2009-04-04 15:33 冰雪女孩

            我剛剛學會了  回復  更多評論   

            # re: ACM PKU 1887 Testing the CATCHER 最長下降(上升)子序列 一維動態規劃 2009-06-03 17:42 大師傅啥的

            我的runtime error 是怎么回事。。。。暈  回復  更多評論   

            # re: ACM PKU 1887 Testing the CATCHER 最長下降(上升)子序列 一維動態規劃 2011-03-26 15:11 to be or not to be

            to be, or not to be
            謝謝  回復  更多評論   

            <2007年9月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            30123456

            導航

            統計

            公告

            MY Email/MSN :mars1021@163.com QQ : 27402040 流牛ζ木馬

            常用鏈接

            留言簿(6)

            隨筆檔案

            相冊

            搜索

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            狠狠色婷婷久久综合频道日韩| 无码国内精品久久人妻| 国产99久久九九精品无码| 久久精品不卡| 久久国产色AV免费观看| 久久精品这里只有精99品| 蜜臀久久99精品久久久久久| 久久精品国产精品亚洲精品| 久久人人爽人人人人片av| 久久97久久97精品免视看| 99久久久久| 国产精品成人99久久久久| 亚洲欧美成人久久综合中文网 | 人妻久久久一区二区三区| 久久精品国产99久久久香蕉| 久久笫一福利免费导航 | 91精品国产91久久| 狠狠色丁香婷婷久久综合五月| 久久久久久久亚洲精品| 日韩精品无码久久久久久| 久久人人爽人人爽人人片AV麻豆| 丁香五月网久久综合| 久久99国产精品久久久| 狠狠色丁香久久婷婷综合_中 | aaa级精品久久久国产片| 久久夜色精品国产噜噜亚洲a| 色综合久久88色综合天天| 久久久精品免费国产四虎| 久久人人添人人爽添人人片牛牛| 国产精品免费久久久久电影网| 97久久国产亚洲精品超碰热 | 久久精品无码一区二区无码| 久久久国产亚洲精品| 亚洲国产日韩欧美综合久久| 狠狠色丁香婷婷综合久久来来去| 亚洲国产精品久久| 色综合久久88色综合天天| 伊人热人久久中文字幕| 精品久久人人做人人爽综合| 国产亚洲精久久久久久无码AV| 国产精品99久久久久久猫咪|