题意:
分析:
- 为了求某个子段的和,我们通过前缀和预处理
- 题目上给出
m
<
=
n
/
3
m<=n/3
m<=n/3 ,所以按照贪心的思想,为了和最大,每个区间一定是要m个长度的连续子段
-
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 代表前
i
i
i 个数,用
j
j
j 个区间,最大值是多少。
- 对于第
i
i
i 个数,如果当前这个区间选择要选择这个数,那么要把以
i
i
i 为最后一个数的连续m个数一起选择,所以状态转移方程是
-
d
p
[
i
−
m
]
[
j
−
1
]
+
(
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
m
]
[
j
−
1
]
+
a
[
i
]
−
a
[
i
−
m
]
)
a
[
i
]
−
a
[
i
−
m
]
)
dp[i-m][j-1]+(dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+a[i]-a[i-m])a[i]-a[i-m])
dp[i−m][j−1]+(dp[i][j]=max(dp[i−1][j],dp[i−m][j−1]+a[i]−a[i−m])a[i]−a[i−m])
#include<iostream>
#include<cstring>
using namespace std;
const int N = 50010;
int a[N],dp[N][5];
int main()
{
int T;cin>>T;
while(T--)
{
memset(dp,0,sizeof dp);
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=2;i<=n;i++) a[i]+=a[i-1];
int m;cin>>m;
for(int i=m;i<=n;i++)
for(int j=3;j>=1;j--)
dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+a[i]-a[i-m]);
cout<<dp[n][3]<<endl;
}
return 0;
}