LOJ P10176 最大连续和题解

每日一题 day29 打卡

Analysis

朴素的DP方程为: dp[i]=max{sum[i]-sum[j-1]};

对于每个i 需要用单调队列维护最小的sum[j-1]

注意：

1.tail初值要置成1，因为i=1时状态要从i=0转移，所以队列中已有一个元素0。

2.对于每个i，要先维护队头，因为j !=i，所以i不会从i转移。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define int long long
 6 #define maxn 200000+10
 7 #define INF 9223372036854775807
 8 using namespace std;
 9 inline int read() 
10 {
11     int x=0;
12     bool f=1;
13     char c=getchar();
14     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
15     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
16     if(f) return x;
17     return 0-x;
18 }
19 inline void write(int x)
20 {
21     if(x<0){putchar('-');x=-x;}
22     if(x>9)write(x/10);
23     putchar(x%10+'0');
24 }
25 int n,m;
26 int a[maxn],sum[maxn],deque[maxn],deque_num[maxn];
27 signed main()
28 {
29     n=read();m=read();
30     for(int i=1;i<=n;i++)
31     {
32         a[i]=read();
33         sum[i]=sum[i-1]+a[i];
34     }
35     int head=1,tail=1,ans=-INF;
36     for(int i=1;i<=n;i++)
37     {
38         while(head<=tail&&deque_num[head]<i-m) head++;
39         ans=max(ans,sum[i]-deque[head]);
40         while(head<=tail&&deque[tail]>=sum[i]) tail--;
41         deque[++tail]=sum[i];
42         deque_num[tail]=i;
43     }
44     write(ans);
45     return 0;
46 }

请各位大佬斧正~~（反正我不认识斧正是什么意思）~~

LOJ P10176 最大连续和 题解

Analysis

LOJ P10176 最大连续和题解