题目传送门
【题目大意】
输入一个长度为$n$的整数序列，从中找出一段长度不超过$m$的连续子序列，使得子序列中所有数的和最大。
【思路分析】
计算“区间和”的问题，一般转化为“两个前缀和相减”的形式进行求解，即问题转化为求$s[x]-s[y]$最大且$x-y\le m$。
首先我们枚举区间的右端点$i$，当$i$固定时，问题就变成：找到一个左端点$j$，其中$j\in[i-m,i-1]$且$s[j]$最小。
那么对于任意两个位置$j$和$k$，如果$k<j<i$并且$s[k]\ge s[j]$，那么对于所有大于等于$i$的右端点，$k$永远不会成为最优选择。由此我们可以知道，可能成为最优选择的策略集合一定是一个“下标位置递增，对应的前缀和也递增”的序列，于是很容易就可以想到队列。
随着右端点$i$的枚举，我们对每个$i$进行如下操作：
1.判断队头决策与$i$的距离是否超过$m$，若是则出队
2.此时队头就是右端点为$i$时，左端点$j$的最优选择
3.不断删除队尾决策，直到队尾对应的$s$值小于$s[i]$，然后把$i$作为一个新的左端点的待选值入队
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define g() getchar() 7 #define rg register 8 #define go(i,a,b) for(rg int i=a;i<=b;i++) 9 #define back(i,a,b) for(rg int i=a;i>=b;i--) 10 #define db double 11 #define ll long long 12 #define il inline 13 #define pf printf 14 using namespace std; 15 int fr(){ 16 int w=0,q=1; 17 char ch=g(); 18 while(ch<'0'||ch>'9'){ 19 if(ch=='-') q=-1; 20 ch=g(); 21 } 22 while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g(); 23 return w*q; 24 } 25 const int N=300002; 26 int n,m,a[N],s[N],q[N],ans; 27 int main(){ 28 //freopen("","r",stdin); 29 //freopen("","w",stdout); 30 n=fr();m=fr(); 31 go(i,1,n) a[i]=fr(),s[i]=s[i-1]+a[i]; 32 rg int l=1,r=1; 33 q[1]=a[1]; 34 go(i,1,n){ 35 while(l<=r&&q[l]<i-m) l++; 36 //判断队头决策的位置与当前右端点的距离是否超过m,若是则出队 37 ans=max(ans,s[i]-s[q[l]]);//更新答案 38 while(l<=r&&s[q[r]]>=s[i]) r--; 39 q[++r]=i;//将i入队 40 } 41 pf("%d\n",ans); 42 return 0; 43 } 代码戳这里
转载于:https://www.cnblogs.com/THWZF/p/11368864.html
