1 条题解
-
3
wdvxdr LV 8 MOD @ 7 年前
先预处理出所有答案,询问时直接输出即可。。
预处理的具体实现可以参照以下代码。
- 1
信息
- 难度
- 8
- 分类
- (无)
- 标签
- (无)
- 递交数
- 18
- 已通过
- 5
- 通过率
- 28%
- 被复制
- 1
- 上传者
先O(n2)预处理出所有答案,询问时直接输出即可。。
预处理的具体实现可以参照以下代码。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
int a[maxn],n,m,t,dp[maxn];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)//枚举区间的长度
{
int sum = 0;
for(int j=1;j<=i;++j)
sum += a[j];
dp[i] = sum;
for(int j = i+1;j<=n;j++)//挪到区间
{
dp[i] = max(dp[i],sum+a[j] - a[j-i]);
sum += a[j] - a[j-i];
}
}
for(int i=n-1;i>0;i--)
dp[i] = max(dp[i+1],dp[i]);
while(m--)
{
scanf("%d",&t);
printf("%d\n",dp[t]);
}
return 0;
}