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

            亚洲中文久久精品无码ww16| 久久久久九九精品影院| 波多野结衣久久一区二区| 久久se精品一区精品二区国产| 午夜不卡888久久| 久久国产视屏| 国产美女亚洲精品久久久综合| 欧美一区二区三区久久综 | 国产精品久久久久AV福利动漫| 无码AV中文字幕久久专区| 嫩草影院久久国产精品| 日韩一区二区三区视频久久| 久久久无码精品亚洲日韩京东传媒| 无码日韩人妻精品久久蜜桃| 国产精品激情综合久久| 亚洲狠狠婷婷综合久久久久| 日本免费久久久久久久网站| 欧美性大战久久久久久 | 久久99国产精品久久久| 久久精品国产第一区二区| 无码人妻久久一区二区三区| 精品久久久久久无码中文字幕 | 青青草国产成人久久91网| 久久无码国产| 久久国产精品国产自线拍免费| 久久精品免费一区二区| 精品99久久aaa一级毛片| 欧美黑人激情性久久| 亚洲精品国精品久久99热| 99久久亚洲综合精品网站| 亚洲国产欧美国产综合久久| 欧美日韩精品久久久久| 久久青草国产手机看片福利盒子| 久久久久久伊人高潮影院| 久久激情五月丁香伊人| 欧美一区二区精品久久| 国产精品99久久精品| 久久精品亚洲日本波多野结衣| 亚洲欧美国产日韩综合久久 | 久久天天躁狠狠躁夜夜96流白浆 | 久久国产色AV免费观看|