您當前位置：首頁 > 互聯(lián)網(wǎng) > zoj 2501 - A Mini Locomotive

zoj 2501 - A Mini Locomotive

來源：程序員人生發(fā)布時間：2014-09-29 12:03:53 閱讀次數(shù)：2398次

題目：有一串數(shù)，從里面取出m個不同的區(qū)間，每個區(qū)間長度不能超過M，使得所取所有數(shù)字和最大。

分析：dp，單調(diào)隊列，區(qū)間最大字段和。因為數(shù)據(jù)都是正的不需要單調(diào)隊列維護（否則要使用）。

區(qū)間最大字段和，求出每個元素作為結束標志的前k項和；取結束位置作為dp狀態(tài)；

然后，利用單調(diào)隊列維護區(qū)間長度，O（1）時間查找滿足長度的最小的前j項和，做差即可。

狀態(tài)：設f（i，j）為前j個數(shù)字，取i個區(qū)間最大和；s（j）為前j個數(shù)字的最大單區(qū)間字段和；

轉(zhuǎn)移：f（i，j）= max（f（i-1，k）+ s（j）） { 其中k ≤ j-M }。

（如果數(shù)據(jù)可以為負，方程不變，用單調(diào)隊列計算單區(qū)間最大字段和即可）

說明：數(shù)據(jù)都是正的，可以用更簡單的方程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; }

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生

------分隔線----------------------------

上一篇 SSH整合中正確配置以及實例

下一篇 偽中介模式(5.5)

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關注

欄目熱點

多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

zoj 2501 - A Mini Locomotive