每日一题 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 }
请各位大佬斧正