LiberOJ 10176 最大连续和单调队列优化DP

题目描述
给你一个长度为\(n\)的整数序列{\(A_1,A_2,...,A_n\)}，要求从中找出一段连续的长度不超过\(m\)的非空子序列，使得这个序列的和最大。

输入格式
第一行为两个整数\(n,m\)；

第二行为\(n\)个用空格分开的整数序列，每个数的绝对值都小于\(1000\) 。

输出格式
仅一个整数，表示连续长度不超过\(m\)的最大非空子序列和。

Solution

和前面的单调队列优化几乎一样，但是有部分改变：
\(dp[i][1] = \max_j(sum[i]-sum[j])\)
注意的一点是，对于\(dp\)数组，初始化得\(-\inf\).

点击查看代码

ll MAX = -inf; int main(){     //ios::sync_with_stdio(false);     n =read(); m  =read(); 	dp[0][0] = dp[0][1] = -inf; 	for(int i=1;i<=n;i++){ 		scanf(%lld, &a[i]); 		sum[i] = ll(sum[i-1]+a[i]); 		MAX = max(MAX, a[i]); 		dp[i][0] = dp[i][1]=-inf; 	} 	//cout<<MAX<<endl; 	int head=0,tail=0; 	q[head]=0;q[tail]=0; 	for(int i=1;i<=n;i++){ 		dp[i][0] = max(dp[i-1][0],dp[i-1][1]); 		while(head<tail && i-q[head]>m)++head; 		dp[i][1] = sum[i]-sum[q[head]]; 		while(head<=tail && -sum[i]>-sum[q[tail]])--tail; 		q[++tail] = i; 	} 	cout<<ll(max(MAX,max(dp[n][0],dp[n][1])))<<endl; }