首页 > 代码库 > 【模拟赛】限宽连续最大和(maxsum)

【模拟赛】限宽连续最大和(maxsum)

2024-07-25 10:35:43   216人阅读


限宽连续最大和(maxsum)
时间限制：1s
空间限制：256M

题目描述：
给定一个n个整数的数列，要求你从中选出长度不超过m的一段，使得这段的和最大。

输入格式：
第一行两个整数n,m表示数列长度和对连续最大和长度的限制
接下来一行n个数描述这个数列

输出格式：
输出一个数表示限宽连续最大和

数据范围与约定：
30% n,m<=10
50% n,m<=100
70% n,m<=1000
100% 1<=n,m<=10^5

样例：

input
4 4
2 -1 -3 4

output
4

input
4 3
2 2 3 4

output
9

 

用到前缀和

i~j之间的和可用sum[i]-sum[j-1]表示

然后每次枚举每一个点i

又因为j的范围是知道的

要使sum[i]-sum[j-1]的和最大 又因sum[i]是确定的 所以只用在j的范围之内选取一个最小值

所以可以用单调队列或线段树维护查找区间最小值

先给开始的70分代码

 1 # include<cstdio> 2 # include<algorithm> 3 using namespace std; 4 const int maxn=1005; 5 int f[maxn][maxn],num[maxn]; 6 int Max,n,m; 7 void solve_1000(){ 8     Max=-999999999; 9     int t=1;10     for(int i=1;i<=n;i++)11     for(int j=t++;j<=n;j++)12     f[i][j]=f[i][j-1]+num[j];13     t=1;14 /*    for(int i=1,tt=0;i<=n;i++,tt=0){15     for(int j=t++;j<=n;j++)16     if(tt++<m)printf("f[%d][%d]=%d ",i,j,f[i][j]);17     printf("\n");18     }*/19     for(int i=1,tt=0;i<=n;i++,tt=0)20     for(int j=t++;j<=n;j++)21     if(tt++<m)Max=max(Max,f[i][j]);22     printf("%d",Max);23 }24 void init(){25     scanf("%d%d",&n,&m);26     for(int i=1;i<=n;i++)27     scanf("%d",&num[i]);28     if(n<=1000)solve_1000();29     else solve30 }31 int main(){32     freopen("maxsum.in","r",stdin);33     freopen("maxsum.out","w",stdout);34     init();35     return 0;36 }
View Code

 

【模拟赛】限宽连续最大和(maxsum)


联系
我们