FOJ 2013 动态规划:求最长子区间

本文主要是介绍FOJ 2013 动态规划:求最长子区间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Problem 2013 A short problem
Accept: 364    Submit: 1104
Time Limit: 1000 mSec    Memory Limit : 32768 KBProblem 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 1Sample Output
1
-1Source
FOJ有奖月赛-2011年03月

前提知识：

hdu 1003题解：
这题其实很hdu的1003题十分相似
先详细介绍一下1003
hdu1003比这题少了一个长度要大于m的限定条件，但是其实还是一样的
假设数字 1 -2 -2 -2 1
那么以1结尾就有：
$a [1]$ $a[1]$
那么以2结尾的就有 $a [1] a [2] o r a [2]$ $a[1]a[2] \\or \\ a[2]$
那么以3结尾的就有 $a [1] a [2] a [3] o r a [2] a [3] o r a [3]$ $a[1]a[2]a[3] \\or \\ a[2]a[3] \\ or \\a[3]$
那么以4结尾的就有 $a [1] a [2] a [3] a [4] o r a [2] a [3] a [4] o r a [3] a [4] o r a [4]$ $a[1]a[2]a[3]a[4] \\ or \\ a[2]a[3]a[4] \\ or \\ a[3]a[4] \\ or \\ a[4]$
因为我们是求最值只要把最值保存下来就好了.
得到转移公式
$d p [i] = m a x (d p [i - 1] + a [i], a [i]);$ $dp[i]=max(dp[i-1]+a[i],a[i]);$

现在是FOJ2013这题的题解

首先我们列出1到m的前缀和
$a 1 a 2 a . . . 3 a m$ $a_1a_2a_3^{...}a_m$
下一项我们可以知道是 $a 1 a 2 a . . . 3 a m a m + 1 o r a 2 a . . . 3 a m a m + 1$ $a_1a_2a_3^{...}a_ma_{m+1} \\ or \\ a_2a_3^{...}a_ma_{m+1}$
同理推出去，得到转移方程
$d p [i] = m a x (d p [i - 1] + a [i], s u m [i] - s u m [i - m])$ $dp[i]=max(dp[i-1]+a[i] , sum[i]-sum[i-m])$
需要记录的是ans但是ans不一定是dp[n]因为最后可能断开，所以我们要找其中最大的dp

#ifdef local
#include    <ctime>
#endif
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <math.h>
#define rep(i,e) for(int i=0;i<e;i++)
#define rep1(i,e) for(int i=1;i<=e;i++)
#define repx(i,x,e) for(int i=x;i<=e;i++)
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define mset(var,val) memset(var,val,sizeof(var))
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define test(a) cout<<a<<endl
#define test2(a,b) cout<<a<<" "<<b<<endl
#define test3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
typedef unsigned long long ull;
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 10;
const int mod = 10000007;
int cnt = 1;
long long  dp[N];
long long sum[N];
int a[N];
void work(){int n,m;scdd(n,m);for(int i =1;i<=n;i++){scd(a[i]);sum[i]=sum[i-1]+a[i];}dp[m-1]=sum[m-1];ll ans=-inf;for(int i=m;i<=n;i++){dp[i]=max(dp[i-1]+a[i],sum[i]-sum[i-m]);if(ans<dp[i]){ans=dp[i];}}printf("%lld\n",ans);
}
int main() {int debug = 0;
#ifdef localdebug = 1;
#endifif (debug) {freopen("in.txt", "r", stdin);//freopen("out", "w", stdout);//printf("debuging output:\n");}int t;scd(t);while(t--)work();
}