青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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有獎(jiǎng)月賽-2011年03月



簡(jiǎn)單的動(dòng)態(tài)規(guī)劃。
F[ i ] 表示以  i 結(jié)尾的長(zhǎng)度大于等于 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 閱讀(1542) 評(píng)論(9)  編輯 收藏 引用 所屬分類: ACM

Feedback

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

表示沒有理解這樣做的道理  回復(fù)  更多評(píng)論   

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

表示沒有理解為什么這樣做、、自己做法:先求不限制的最大子段和,然后對(duì)m+1—n個(gè),每個(gè)ans = max(msum+f[i-m], msum);求得其最大值就可以了。  回復(fù)  更多評(píng)論   

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

@xx
若你的 msum 是指當(dāng)前以 i 結(jié)尾的長(zhǎng)度為 m 的序列的和,則
我的 maxA <==> 你的 msum+f[i-m]
我的 maxB <==> 你的 msum
  回復(fù)  更多評(píng)論   

# re: A short problem, FZU 2011年3月月賽之 D, FZU 2013 2011-03-21 22:47 銀志圓

細(xì)問 你的狀態(tài)轉(zhuǎn)移方程是?有點(diǎn)不明白f與d之間的關(guān)系  回復(fù)  更多評(píng)論   

# re: A short problem, FZU 2011年3月月賽之 D, FZU 2013 2011-03-21 22:49 銀志圓

f與s
  回復(fù)  更多評(píng)論   

# 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 ]
);
已加入本文
  回復(fù)  更多評(píng)論   

# re: A short problem, FZU 2011年3月月賽之 D, FZU 2013 2011-03-22 07:07 銀志圓

@coreBugZJ
明白了 Thank you!
  回復(fù)  更多評(píng)論   

# re: A short problem, FZU 2011年3月月賽之 D, FZU 2013 2011-03-22 09:31 銀志圓

哥們 fzu第一道題怎么做啊 我的一致wr 汗  回復(fù)  更多評(píng)論   

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

@銀志圓
第一題是我隊(duì)友做的,我還沒看  回復(fù)  更多評(píng)論   


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲精品一区二区三区福利| 国产精品国产| 韩国成人精品a∨在线观看| 欧美在线3区| 久久精品亚洲乱码伦伦中文| 亚洲成人在线网站| 亚洲国产合集| 国产精品国产三级国产普通话三级| 午夜精品免费在线| 久久精品91久久香蕉加勒比| 亚洲精品国产精品国自产在线| 日韩亚洲成人av在线| 国产精品免费观看视频| 美女视频黄免费的久久| 欧美日韩国语| 久久综合九色九九| 欧美日韩国产免费| 久久精品系列| 欧美激情第二页| 亚洲欧美经典视频| 麻豆成人精品| 欧美一区二区在线播放| 你懂的成人av| 久久国产福利国产秒拍| 欧美激情在线播放| 久久精品中文字幕一区| 欧美精品一区二区三区四区| 久久久久久夜| 欧美性事免费在线观看| 亚洲电影免费| 国产一区二区你懂的| 亚洲激精日韩激精欧美精品| 国产亚洲欧美另类一区二区三区| 亚洲精品一区二区三区不| 极品尤物一区二区三区| 一区二区免费在线播放| 亚洲日本乱码在线观看| 欧美在线在线| 欧美怡红院视频一区二区三区| 欧美韩国日本综合| 欧美α欧美αv大片| 国产视频观看一区| 亚洲小说欧美另类婷婷| 妖精成人www高清在线观看| 久久久久免费| 久久亚洲精品视频| 国产无一区二区| 亚洲欧美国产精品va在线观看 | 欧美理论在线播放| 久久免费少妇高潮久久精品99| 国产精品日韩精品欧美精品| 99re8这里有精品热视频免费| 亚洲国产欧美不卡在线观看| 久久久久综合网| 卡通动漫国产精品| 海角社区69精品视频| 欧美在线视频一区二区| 欧美中文字幕在线| 国产欧美综合一区二区三区| 亚洲制服少妇| 欧美影院在线| 狠狠色丁香久久综合频道| 久久精品1区| 欧美.www| 日韩视频免费在线观看| 欧美激情一区二区三区在线视频观看| 欧美激情五月| 一本久久a久久精品亚洲| 欧美日韩中文在线| 中文久久乱码一区二区| 久久国产精品久久精品国产| 国产主播精品在线| 久久视频在线看| 亚洲黄色免费| 在线一区欧美| 国产精品亚发布| 久久黄色网页| 亚洲国产老妈| 先锋影音国产一区| 国内精品一区二区| 欧美成人精品在线播放| 99热免费精品| 久久精品91| 亚洲精品乱码久久久久久黑人 | 欧美日韩一区二区视频在线| 亚洲视频电影在线| 裸体素人女欧美日韩| 99热精品在线观看| 国产欧美日韩在线| 免播放器亚洲| 亚洲欧美不卡| 亚洲国产精品久久人人爱蜜臀| 亚洲天堂第二页| 国产亚洲视频在线| 欧美精品日韩| 欧美一区永久视频免费观看| 亚洲国产三级网| 久久久久久网站| 一区二区三区你懂的| 韩日视频一区| 国产精品成人aaaaa网站| 久久久国产精品亚洲一区| 亚洲精选一区二区| 美女网站在线免费欧美精品| 在线一区二区三区四区| 激情久久久久久| 国产精品视频免费| 欧美黄色片免费观看| 欧美亚洲在线视频| 99成人在线| 亚洲黄色在线视频| 免费不卡视频| 久久精品视频导航| 亚洲一区二区在线看| 亚洲精品极品| 亚洲高清一区二| 国产日韩在线一区二区三区| 欧美三区在线视频| 欧美精品日韩www.p站| 久热精品视频| 久久久999| 久久精品亚洲乱码伦伦中文| 亚洲专区一区| 亚洲一区免费| 亚洲一区精品在线| 亚洲网站视频福利| 日韩香蕉视频| 亚洲精品一区在线观看香蕉| 最新国产拍偷乱拍精品 | 午夜免费久久久久| 亚洲一区在线观看视频 | 欧美在线视频不卡| 亚洲综合色网站| 亚洲婷婷综合久久一本伊一区| 一本大道久久a久久精二百| 亚洲开发第一视频在线播放| 亚洲第一毛片| 亚洲国产色一区| 亚洲免费大片| 一区二区日韩伦理片| 亚洲天堂免费观看| 亚洲一区二区三区免费在线观看 | 午夜视频久久久| 久久国产福利国产秒拍| 久久精品一二三| 久久色在线观看| 欧美aⅴ99久久黑人专区| 欧美mv日韩mv国产网站app| 欧美激情视频给我| 亚洲人成啪啪网站| 夜夜爽www精品| 亚洲欧美日韩爽爽影院| 久久久久国内| 欧美第一黄色网| 国产精品扒开腿做爽爽爽软件| 国产精品一区二区三区乱码 | 欧美屁股在线| 国产精品久久久久久超碰| 国产日韩欧美综合一区| 在线国产日韩| 在线视频欧美日韩精品| 欧美在线不卡| 欧美国内亚洲| 一区二区三区精品视频| 性欧美videos另类喷潮| 蜜臀91精品一区二区三区| 欧美精品啪啪| 国产日韩欧美综合一区| 亚洲人妖在线| 性做久久久久久免费观看欧美| 久久深夜福利| 一本久道久久综合狠狠爱| 午夜精品免费| 欧美精品性视频| 国产一区二区中文| a91a精品视频在线观看| 久久精品夜色噜噜亚洲aⅴ| 亚洲国产视频一区二区| 性亚洲最疯狂xxxx高清| 欧美经典一区二区| 国产在线成人| 亚洲欧美成人一区二区在线电影| 久久综合久久久| 在线视频精品| 欧美高清在线视频观看不卡| 国产欧美日韩亚洲一区二区三区| 日韩视频免费在线观看| 久久综合激情| 午夜精品久久久99热福利| 欧美日韩免费一区二区三区视频| 国产一区二区视频在线观看| 亚洲一区二区精品视频| 亚洲国产成人久久综合| 欧美专区日韩视频| 国产精品日本一区二区| 一区二区三区国产| 亚洲国产精品久久| 免费看av成人| 亚洲成人直播| 你懂的网址国产 欧美|