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

            色诱久久久久综合网ywww | 久久国产精品一区| 国产精品久久久久国产A级| 97久久国产亚洲精品超碰热| 色综合久久久久综合体桃花网| 性欧美大战久久久久久久久 | 好久久免费视频高清| 伊人久久大香线焦AV综合影院| 国产综合精品久久亚洲| 99久久国产精品免费一区二区 | 亚洲精品乱码久久久久久按摩 | 一本久久a久久精品综合香蕉| 久久国产免费直播| 久久精品国产精品亚洲| 狠狠精品久久久无码中文字幕| 久久精品国产久精国产| 久久国产免费直播| 2021国内久久精品| 综合久久给合久久狠狠狠97色| 99精品久久精品一区二区| 色综合久久综合中文综合网| 人人狠狠综合久久亚洲高清| 国产精品久久成人影院| 久久久久人妻一区精品色| 一本久道久久综合狠狠爱| 午夜精品久久影院蜜桃| 久久亚洲色一区二区三区| 国产精品久久久久久久久软件| 欧美黑人激情性久久| 国产精品99久久99久久久| 久久线看观看精品香蕉国产| 久久精品亚洲精品国产欧美| 欧美日韩成人精品久久久免费看| 久久er国产精品免费观看8| 亚洲国产精品成人久久蜜臀| 久久久久成人精品无码中文字幕| 国产精品久久久久久吹潮| 久久精品99无色码中文字幕| 久久久久久久久久久精品尤物 | 久久国产亚洲精品无码| 亚洲国产精品成人久久蜜臀|