Soledad_S @ 2018-12-05 22:07:28
手工(AC)
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<deque>
using namespace std;
long long e[100005],s[100005],f[100005][2];
long long q[100005];
int n,k;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>e[i],s[i]=s[i-1]+e[i];
int l=1,r=1;
for(int i=1;i<=n;i++){
f[i][0]=max(f[i-1][0],f[i-1][1]);
while(l<=r&&q[l]<i-k)l++;
f[i][1]=f[q[l]][0]+s[i]-s[q[l]];
while(l<=r&&f[i][0]-s[i]>f[q[r]][0]-s[q[r]])r--;
q[++r]=i;
}
cout<<max(f[n][1],f[n][0])<<endl;
return 0;
}
STL(10分)
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<deque>
using namespace std;
long long e[100005],s[100005],f[100005][2];
deque<long long>q;
int n,k;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>e[i],s[i]=s[i-1]+e[i];
for(int i=1;i<=n;i++){
f[i][0]=max(f[i-1][0],f[i-1][1]);
while(!q.empty()&&q.front()<i-k)q.pop_front();
f[i][1]=f[q.front()][0]+s[i]-s[q.front()];
while(!q.empty()&&f[i][0]-s[i]>f[q.back()][0]-s[q.back()])q.pop_back();
q.push_back(i);
}
cout<<max(f[n][1],f[n][0])<<endl;
return 0;
}
by memset0 @ 2018-12-05 22:08:07
@Soledad 你写挂了
by Soledad_S @ 2018-12-05 22:08:57
@memset0
Where I died???
by GKxx @ 2018-12-05 22:54:24
f[i][1]=f[q.front()][0]+s[i]-s[q.front()];
这一句在执行的时候队列可能是空的,q.front()会抛出异常而RE
by 吾王美如画 @ 2018-12-05 23:11:19
我也是stl只有10分QAQ