日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內(nèi)最全I(xiàn)T社區(qū)平臺(tái) 聯(lián)系我們 | 收藏本站
阿里云優(yōu)惠2
您當(dāng)前位置:首頁 > 互聯(lián)網(wǎng) > zoj 2501 - A Mini Locomotive

zoj 2501 - A Mini Locomotive

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

題目:有一串?dāng)?shù),從里面取出m個(gè)不同的區(qū)間,每個(gè)區(qū)間長度不能超過M,使得所取所有數(shù)字和最大。

分析:dp,單調(diào)隊(duì)列,區(qū)間最大字段和。因?yàn)閿?shù)據(jù)都是正的不需要單調(diào)隊(duì)列維護(hù)(否則要使用)。

            區(qū)間最大字段和,求出每個(gè)元素作為結(jié)束標(biāo)志的前k項(xiàng)和;取結(jié)束位置作為dp狀態(tài);

            然后,利用單調(diào)隊(duì)列維護(hù)區(qū)間長度,O(1)時(shí)間查找滿足長度的最小的前j項(xiàng)和,做差即可。

            狀態(tài):設(shè)f(i,j)為前j個(gè)數(shù)字,取i個(gè)區(qū)間最大和;s(j)為前j個(gè)數(shù)字的最大單區(qū)間字段和;

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

            (如果數(shù)據(jù)可以為負(fù),方程不變,用單調(diào)隊(duì)列計(jì)算單區(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)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關(guān)閉
程序員人生
主站蜘蛛池模板: 欧美日韩中文字幕在线 | 九一在线| 免费一级欧美片在线观看网站 | 国产一区二| 免费三级黄色 | 天堂av在线免费观看 | a成人 | 精品国产1区 | 成人久久久久久 | 国产精品一区二区久久 | 国产成人精品久久二区二区91 | 欧美成人一级视频 | 免费一级毛片电影 | 欧美极品一区二区三区 | 成人免费大片在线观看 | 中文字幕福利视频 | 久久婷婷国产麻豆91天堂徐州 | 亚洲一区二区三区影院 | 精品国产三级 | 欧美三级网站 | 国产精品麻豆视频 | 91成人入口 | 黄色毛片免费观看 | www.日韩精品 | av资源网站| 欧美日韩第一区 | 色老板视频 | 日韩精品一区二区三区免费视频 | 国产一区二区欧美 | 欧美高清18| 亚洲精品成人在线 | 久久精品九九 | 成人在线观看免费 | 欧美日韩综合在线 | 国产精品成人一区 | 欧美一级黄色片子 | av在线免费观看网址 | 黄色高清美女免费网站 | 欧洲一级黄 | 国产乱码一区二区三区 | 国内av毛片 |