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

            coreBugZJ

            此 blog 已棄。

            Dark Parth, 1004, 2011 Multi-University Training Contest 10

            Dark Parth

            TimeLimit: 1 Second   MemoryLimit: 64 Megabyte

            Totalsubmit: 470   Accepted: 114  

            Description

            In the dark path, the single figure is walking difficultly in the listless rainfall. No one knows his real destination.

            ‘Young, have you ever tasted the loneliness walking in dark path; have you ever run about madly just to avoid the pain in the deep heart?'
            After BiYao's death, XiaoFan changed to GuiLi .Running in such darkness, leaving the rain wet out his clothes, leaving the darkness cover up his eyes, he will never regret!

            Now, we separate the path into n parts with the same length (1<=N<=1000).Every part has its value Ai (-1000<=Ai<=1000). If Xiaofan walks through the ith part of the path, he will get the hurt Ai. His trump ShaoHuoGun will give him S chances to fly (1<=S<=100). Every chance can help him get through one part of the path without any hurt. But there’s a limit: The length of his fly Si should be longer than La and shorter than Lb (1<=La<=Si<=Lb<=n).
            Your job is to find the best way for XiaoFan to have the least hurt.
            Hit: Two different fly paths can't cover each other, and times of fly can be fewer than the given times S.


            Input

            There are several test cases. The first line is an integer N, then the second line have three integers Lb, La, S, then followed N integers A1.A2…An.The test end by n = 0.


            Output

            The value of least hurt.


            Sample Input

            10
            3 2 3
            3 1 -5 -9 2 -1 1 -7 9 10

            10
            4 3 4
            -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

            0


            Sample Output

            -21
            -10


            Source

            [p][/p]





            DP

             1 #include <stdio.h>
             2 #include <string.h>
             3 
             4 #define  N   1009
             5 #define  S   109
             6 #define  OO  0x3F3F3F3F
             7 
             8 int n, lb, la, s, a[ N ], sa[ N ], f[ N ][ S ];
             9 
            10 int solve() {
            11         int i, j, v, tmp, tmp0;
            12 
            13         memset( f, 0x3Fsizeof(f) );
            14 
            15         for ( i = 0; i <= n; ++i ) {
            16                 f[ i ][ 0 ] = sa[ i ];
            17         }
            18         for ( i = 1; i <= n; ++i ) {
            19                 for ( j = 1; j <= s; ++j ) {
            20                         tmp = f[ i - 1 ][ j ] + a[ i ];
            21                         for ( v = la; (v <= lb) && (v <= i); ++v ) {
            22                                 tmp0 = f[ i - v ][ j - 1 ];
            23                                 if ( tmp0 < tmp ) {
            24                                         tmp = tmp0;
            25                                 }
            26                         }
            27                         f[ i ][ j ] = tmp;
            28                 }
            29         }
            30 
            31         tmp = f[ n ][ 0 ];
            32         for ( j = 1; j <= s; ++j ) {
            33                 if ( tmp > f[ n ][ j ] ) {
            34                         tmp = f[ n ][ j ];
            35                 }
            36         }
            37         return tmp;
            38 }
            39 
            40 int main() {
            41         int i;
            42         for ( ; ; ) {
            43                 scanf( "%d"&n );
            44                 if ( n == 0 ) {
            45                         break;
            46                 }
            47                 scanf( "%d%d%d"&lb, &la, &s );
            48                 sa[ 0 ] = 0;
            49                 for ( i = 1; i <= n; ++i ) {
            50                         scanf( "%d", a+i );
            51                         sa[ i ] = sa[ i - 1 ] + a[ i ];
            52                 }
            53                 printf( "%d\n", solve() );
            54         }
            55         return 0;
            56 }
            57 

            posted on 2011-08-11 17:24 coreBugZJ 閱讀(305) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm

            一本久道久久综合狠狠爱| 久久亚洲春色中文字幕久久久 | 久久精品国产99国产精品澳门| 国产精品一区二区久久国产| 91精品国产高清久久久久久国产嫩草| 97久久精品无码一区二区| 久久99精品久久久久久噜噜| 久久久亚洲精品蜜桃臀| 亚洲国产另类久久久精品| 国产91久久综合| 无码超乳爆乳中文字幕久久| 久久久这里有精品中文字幕| 人妻无码久久一区二区三区免费 | 国产激情久久久久影院老熟女免费| 久久精品国产99久久香蕉| 一本久久a久久精品vr综合| 久久国产精品国语对白| 久久av无码专区亚洲av桃花岛| 精品久久久久久无码人妻蜜桃| 无遮挡粉嫩小泬久久久久久久| 久久久精品久久久久久 | 亚洲国产精品无码久久| 国产激情久久久久影院小草| 亚洲国产另类久久久精品 | 成人a毛片久久免费播放| 色欲综合久久中文字幕网| 久久国内免费视频| 久久人人爽人人澡人人高潮AV| 国内精品久久久久久久97牛牛| 精品国产青草久久久久福利| 久久亚洲电影| 久久频这里精品99香蕉久| 久久精品成人一区二区三区| 99久久精品免费看国产免费| 国产精品久久网| 久久精品国产91久久综合麻豆自制 | 久久久精品视频免费观看| 国内精品久久久久国产盗摄| 一本大道久久a久久精品综合| 日本精品久久久久中文字幕8| 精品无码久久久久久尤物|