zoj 2501 - A Mini Locomotive
来源：程序员人生 发布时间：2014-09-29 12:03:53 阅读次数：2267次
题目：有一串数，从里面取出m个不同的区间，每个区间长度不能超过M，使得所取所有数字和最大。
分析：dp，单调队列，区间最大字段和。因为数据都是正的不需要单调队列维护（否则要使用）。
区间最大字段和，求出每个元素作为结束标志的前k项和；取结束位置作为dp状态；
然后，利用单调队列维护区间长度，O（1）时间查找满足长度的最小的前j项和，做差即可。
状态：设f（i，j）为前j个数字，取i个区间最大和；s（j）为前j个数字的最大单区间字段和；
转移：f（i，j）= max（f（i-1，k）+ s（j）） { 其中k ≤ j-M }。
（如果数据可以为负，方程不变，用单调队列计算单区间最大字段和即可）
说明：数据都是正的，可以用更简单的方程dp。。。（2011-11-02 00:16）
#include <stdio.h>
#include <stdlib.h>
int main()
{
int F[ 4 ][ 50005 ];
int T,N,M,t,i,m,l,r,s;
while ( ~scanf("%d",&T) )
for ( t = 1 ; t <= T ; ++ t ) {
scanf("%d",&N);
for ( i = 1 ; i <= N ; ++ i )
scanf("%d",&F[ 0 ][ i ]);
scanf("%d",&M);
for ( s = 0,l = i = 1 ; i <= N ; ++ i ) {
s += F[ 0 ][ i ];
if ( i-l >= M ) s -= F[ 0 ][ l ++ ];
F[ 1 ][ i ] = s;
}
for ( m = 2 ; m <= 3 ; ++ m )
for ( s = 0,i = 1 ; i <= N ; ++ i ) {
if ( s < F[ m-1 ][ i-M ] )
s = F[ m-1 ][ i-M ];
F[ m ][ i ] = s + F[ 1 ][ i ];
}
int max = 0;
for ( i = 1 ; i <= N ; ++ i )
if ( max < F[ 3 ][ i ] )
max = F[ 3 ][ i ];
printf("%d
",max);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
