Problem 2013 A short problem
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
The description of this problem is very short. Now give you a string(length N), and ask you the max sum of the substring which the length can't small than M.
Input
The first line is one integer T(T≤20) indicates the number of the test cases. Then for every case, the first line is two integer N(1≤N≤1000000) and M(1≤M≤N).
Then one line contains N integer indicate the number. All the number is between -10000 and 10000.
Output
Output one line with an integer.
Sample Input
2
5 1
1 -2 -2 -2 1
5 2
1 -2 -2 -2 1
Sample Output
1
-1
Source
FOJ有獎(jiǎng)月賽-2011年03月
簡單的動(dòng)態(tài)規(guī)劃。
F[ i ] 表示以 i 結(jié)尾的長度大于等于 m 的序列的最大和。
F[ i ] = max( F[ i - 1 ] + A[ i ], A[ i ] + A[ i-1 ] + A[ i-2 ] + ... + A[ i-m+1 ] );
1 #include <stdio.h>
2
3 typedef long long Lint;
4 #define OFT "%lld\n"
5
6 #define L 1000009
7
8 int n, m;
9 int a[ L ];
10 Lint s[ L ], f[ L ], ans;
11
12 int main() {
13 int td, i;
14 Lint maxA, maxB;
15 scanf( "%d", &td );
16 while ( td-- > 0 ) {
17 scanf( "%d%d", &n, &m );
18 s[ 0 ] = a[ 0 ] = 0;
19 for ( i = 1; i <= n; ++i ) {
20 scanf( "%d", a + i );
21 s[ i ] = s[ i - 1 ] + a[ i ];
22 }
23 f[ m - 1 ] = s[ m - 1 ];
24 ans = s[ m ];
25 for ( i = m; i <= n; ++i ) {
26 maxA = f[ i - 1 ] + a[ i ];
27 maxB = s[ i ] - s[ i - m ];
28 f[ i ] = ( maxA < maxB ? maxB : maxA );
29 if ( f[ i ] > ans ) {
30 ans = f[ i ];
31 }
32 }
33 printf( OFT, ans );
34 }
35 return 0;
36 }
37