1947: #514. 「LibreOJ β Round #2」模拟只会猜题意
Time Limit: 1 Sec
Memory Limit: 256 MB
Submit: 86
Solved: 23
[
Submit][
Status][
Web Board]
Description
给定一个长度为 nnn 的序列 AAA 。
定义 f(l,r)=∑i=lrAif(l,r)=\sum_{i=l}^{r} A_{i}f(l,r)=∑i=lrAi。
询问 mmm 次，每次询问一个数字 xxx，请求出所有满足 r−l+1≥xr-l+1 \ge xr−l+1≥x 区间 [l,r][l,r][l,r] 中最大的 f(l,r)f(l,r)f(l,r)。
Input
第一行两个数，表示 nnn 和 mmm 。 之后 nnn 个数，表示序列 AAA。 之后 mmm 行每行一个数 xxx，表示询问 xxx 。
Output
输出 mmm 行，每行一个答案，表示最大的 f(l,r)f(l,r)f(l,r) 。
Sample Input
5 5
1 2 3 4 5
1
2
3
4
5
Sample Output
15
15
15
15
15
HINT
1≤x≤n≤1041 \leq x \leq n \leq 10^{4}1≤x≤n≤104 ，0≤m≤1050 \leq m \leq 10^{5}0≤m≤105 ， ∣Ai∣≤104|A_i| \leq 10^{4}∣Ai∣≤104 。
【分析】
说一下题意：求区间长度>=x的最大区间和
预处理出前缀和，然后n^2爆搜所有长度的区间和，求所有长度为i的最大区间和
因为存在多次询问，所以需要预处理一下，另外因为问的是区间长度>=x,
所以长度为i的区间和能够影响所有比i小的区间和，比如长度为10的区间可能能够作为x=6的答案
【代码】
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int a[100000];
int f[100000];
int sum[100000];
int main()
{
int n,m;
while (~scanf("%d%d",&n,&m))
{
memset(f,-INF,sizeof(f));
for (int i=0;i<n;i++) scanf("%d",&a[i]);
sum[0]=a[0];
for (int i=1;i<n;i++) sum[i]=sum[i-1]+a[i];
sum[n]=sum[n-1];
for (int i=0;i<n;i++)
for (int j=i;j<n;j++)
if (sum[j]-sum[i]+a[i]>f[j-i+1])
f[j-i+1]=sum[j]-sum[i]+a[i];
for (int i=n-1;i>=0;i--) f[i]=max(f[i],f[i+1]);
for (int i=0;i<m;i++)
{
int x;scanf("%d",&x);
printf("%d\n",f[x]);
}
}
return 0;
}
