coreBugZJ

此 blog 已弃。

A short problem, FZU 2011年3月月赛之 D, FZU 2013

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有奖月赛-2011年03月



简单的动态规划。
F[ i ] 表示以  i 结尾的长度大于等于 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 

posted on 2011-03-20 18:40 coreBugZJ 阅读(1474) 评论(9)  编辑 收藏 引用 所属分类: ACM

Feedback

# re: A short problem, FZU 2011年3月月赛之 D, FZU 2013 2011-03-21 12:51 xx

表示没有理解这样做的道理  回复  更多评论   

# re: A short problem, FZU 2011年3月月赛之 D, FZU 2013 2011-03-21 12:52 xx

表示没有理解为什么这样做、、自己做法:先求不限制的最大子段和,然后对m+1—n个,每个ans = max(msum+f[i-m], msum);求得其最大值就可以了。  回复  更多评论   

# re: A short problem, FZU 2011年3月月赛之 D, FZU 2013 2011-03-21 17:40 coreBugZJ

@xx
若你的 msum 是指当前以 i 结尾的长度为 m 的序列的和,则
我的 maxA <==> 你的 msum+f[i-m]
我的 maxB <==> 你的 msum
  回复  更多评论   

# re: A short problem, FZU 2011年3月月赛之 D, FZU 2013 2011-03-21 22:47 银志圆

细问 你的状态转移方程是?有点不明白f与d之间的关系  回复  更多评论   

# re: A short problem, FZU 2011年3月月赛之 D, FZU 2013 2011-03-21 22:49 银志圆

f与s
  回复  更多评论   

# re: A short problem, FZU 2011年3月月赛之 D, FZU 2013 2011-03-21 23:00 coreBugZJ

@银志圆
F[ i ] = max
(
F[ i - 1 ] + A[ i ],
A[ i ] + A[ i-1 ] + A[ i-2 ] + ... + A[ i-m+1 ]
);
已加入本文
  回复  更多评论   

# re: A short problem, FZU 2011年3月月赛之 D, FZU 2013 2011-03-22 07:07 银志圆

@coreBugZJ
明白了 Thank you!
  回复  更多评论   

# re: A short problem, FZU 2011年3月月赛之 D, FZU 2013 2011-03-22 09:31 银志圆

哥们 fzu第一道题怎么做啊 我的一致wr 汗  回复  更多评论   

# re: A short problem, FZU 2011年3月月赛之 D, FZU 2013 2011-03-22 15:56 coreBugZJ

@银志圆
第一题是我队友做的,我还没看  回复  更多评论   



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理