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, 0x3F, sizeof(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