• <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>
            posts - 21, comments - 2, trackbacks - 0, articles - 0

            HDU 1087 Super Jumping

            Posted on 2011-10-03 01:28 acpeng 閱讀(294) 評論(0)  編輯 收藏 引用 所屬分類: ACM程序
            題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1087
            Problem Description
            Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now.


            The game can be played by two or more than two players. It consists of a chessboard(棋盤)and some chessmen(棋子), and all chessmen are marked by a positive integer or “start” or “end”. The player starts from start-point and must jumps into end-point finally. In the course of jumping, the player will visit the chessmen in the path, but everyone must jumps from one chessman to another absolutely bigger (you can assume start-point is a minimum and end-point is a maximum.). And all players cannot go backwards. One jumping can go from a chessman to next, also can go across many chessmen, and even you can straightly get to end-point from start-point. Of course you get zero point in this situation. A player is a winner if and only if he can get a bigger score according to his jumping solution. Note that your score comes from the sum of value on the chessmen in you jumping path.
            Your task is to output the maximum value according to the given chessmen list.
            Input
            Input contains multiple test cases. Each test case is described in a line as follow:
            N value_1 value_2 …value_N
            It is guarantied that N is not more than 1000 and all value_i are in the range of 32-int.
            A test case starting with 0 terminates the input and this test case is not to be processed.
            Output
            For each case, print the maximum according to rules, and one line one case.

            Sample Input
            3 1 3 2 4 1 2 3 4 4 3 3 2 1 0
            Sample Output
            4 10 3













            典型的入門級DP題,解題思路:
            定義MaxIncludeEnd數組,令MaxIncludeEnd[i]表示以a[i]結尾的最大和,那么
            MaxIncludeEnd[i]=max{ MaxIncludeEnd[i] , a[j]<a[i] ? (MaxIncludeEnd[j]+a[i]) :-1; }
            其中j=0 to i-1;MaxIncludeEnd[i]的初始值為a[i]。
            #include<stdio.h>
            int a[1003],MaxIncludeEnd[1003];
            int main()
            {
                
            int n,max,i,j;
                
            while(scanf("%d",&n),n)
                
            {
                    
            for(i=0;i<n;i++)
                    
            {
                        scanf(
            "%d",&a[i]);
                        MaxIncludeEnd[i]
            =a[i];
                    }

                    max
            =MaxIncludeEnd[0];
                    
            for(i=0;i<n;i++)
                    
            {
                        
            for(j=0;j<i;j++)
                        
            {
                            
            if(a[j]<a[i] && MaxIncludeEnd[j]+a[i]>MaxIncludeEnd[i])
                                MaxIncludeEnd[i]
            =MaxIncludeEnd[j]+a[i];
                        }

                        
            if(max<MaxIncludeEnd[i])max=MaxIncludeEnd[i];
                    }

                    printf(
            "%d\n",max);
                }

                
            return 0;
            }



            99久久精品国产一区二区三区| 久久综合给合久久狠狠狠97色| 成人久久精品一区二区三区| 久久中文字幕一区二区| 久久久久99精品成人片牛牛影视| 婷婷久久精品国产| 久久精品国产亚洲AV麻豆网站| 久久久久久久尹人综合网亚洲| 欧美粉嫩小泬久久久久久久| 热re99久久精品国99热| 精品乱码久久久久久夜夜嗨| 亚洲香蕉网久久综合影视| 日本一区精品久久久久影院| 欧美伊人久久大香线蕉综合| 久久综合狠狠色综合伊人| 人妻无码αv中文字幕久久琪琪布| 久久er热视频在这里精品| 免费精品国产日韩热久久| 一本伊大人香蕉久久网手机| 日本欧美久久久久免费播放网 | 亚洲乱亚洲乱淫久久| 人妻无码精品久久亚瑟影视| 精品久久久久久无码人妻热| 91久久精品91久久性色| 久久久久久久久66精品片| 亚洲国产精品热久久| 99久久久精品免费观看国产| 日产精品99久久久久久| 久久夜色精品国产网站| 久久夜色精品国产亚洲| 欧美亚洲国产精品久久| 区久久AAA片69亚洲| 成人综合久久精品色婷婷| 香蕉aa三级久久毛片| 久久亚洲2019中文字幕| 久久国产精品免费| 久久亚洲国产成人精品无码区| 久久亚洲AV永久无码精品| 久久久噜噜噜久久| 婷婷久久综合九色综合绿巨人| 日批日出水久久亚洲精品tv|