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



            亚洲欧美成人久久综合中文网| 99999久久久久久亚洲| 99久久精品久久久久久清纯| 99久久亚洲综合精品网站| 97精品伊人久久久大香线蕉| 精品国产青草久久久久福利| 人妻少妇精品久久| 无码国产69精品久久久久网站| 久久精品国产半推半就| 精品久久久久中文字| 亚洲∧v久久久无码精品| 91久久精品视频| 亚洲欧美国产精品专区久久 | 99久久国产综合精品成人影院| 久久黄视频| 久久se精品一区精品二区| 婷婷久久精品国产| 狠狠色丁香婷婷综合久久来| 久久亚洲精品成人无码网站| 久久精品国产只有精品2020| 国产精品久久久久蜜芽| 国产一级持黄大片99久久| 午夜精品久久久久久久久| 亚洲精品成人网久久久久久| 99久久婷婷国产一区二区| 久久精品亚洲精品国产色婷| 久久精品国产2020| 久久久这里只有精品加勒比| 亚洲狠狠久久综合一区77777 | 欧美熟妇另类久久久久久不卡| 久久综合九色欧美综合狠狠 | 久久免费小视频| 久久久久久亚洲Av无码精品专口| 亚洲性久久久影院| 久久天天躁狠狠躁夜夜av浪潮| 国产精品内射久久久久欢欢 | 一本色道久久88综合日韩精品 | 中文国产成人精品久久不卡| 综合久久久久久中文字幕亚洲国产国产综合一区首 | 日本欧美久久久久免费播放网| 久久精品国产欧美日韩99热|