STL与手工有区别吗?

P2627 [USACO11OPEN] Mowing the Lawn G

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


|