萌新刚学OI2天,请问这道单调队列优化dp哪里出错了?

P2627 [USACO11OPEN] Mowing the Lawn G

张鑫杰 @ 2018-10-24 19:09:01

#include<bits/stdc++.h>
#define ini(x,y) memset(x,y,sizeof(x))
#define all(x) x.begin(),x.end()
#define F(x,y,z) for(register int x=y;x<=z;++x)
#define D(x,y,z) for(register int x=y;x>=z;--x)
#define cint const int&
using namespace std;
const int MAXN=static_cast<int>(1e5)+100;
const long long INF=0x3f3f3f3f3f3f3f3f;
const int oo=0x3f3f3f3f;
#define int long long
inline int read()
{
  int x = 0, y = 1, c = getchar();
  while (c>'9' || c<'0')
  {
    if (c == '-')y = -1;
    c = getchar();
  }
  while (c >= '0'&&c <= '9')
  {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * y;
};
int data[MAXN];
struct node{
    int data,pos;
    node(int d=0,int p=0){
        data=d;
        pos=p;
    }
};
class Deque{
    private:
    //#define node int
    node que[MAXN];
    int head=0,tail=0,_size=0;
    const int MOD=2e5+1;
    public:
    void push_back(const node&i){
        que[tail++]=i;
        _size++;
        tail%=MOD;
    }
    void push_front(const node&i){
        que[--head]=i;
        _size++;
        head%=MOD;
    }
    void pop_back(){
        tail--;
        _size--;
        tail%=MOD;
    }
    void pop_front(){
        head++;
        _size--;
        head%=MOD;
    }
    node front(){
        return que[head];
    }
    node back(){
        return que[tail-1];
    }
    int size(){
        return _size;
    }
    bool empty(){
        return !_size;
    }
    //#undef node
};
Deque q;
int sum[MAXN],f[MAXN][2];
signed main(){
    int n=read(),k=read();
    F(i,1,n){
        sum[i]=sum[i-1]+read();
    }
    F(i,1,n){
        f[i][0]=max(f[i-1][0],f[i-1][1]);
        while(!q.empty()&&q.front().pos<=i-k){
            q.pop_front();
        }
        f[i][1]=((q.empty())?0:q.front().data)+sum[i];
        while(!q.empty()&&q.back().data<=f[i][0]-sum[i]){
            q.pop_back();
        }
        q.push_back(node(i,f[i][0]-sum[i]));
        //cout<<f[i][0]<<" "<<f[i][1]<<endl;
    }
    printf("%lld",max(f[n][0],f[n][1]));
    return 0;
}

会选择超出k的值,我表示很奇怪的


by あおあんどん @ 2018-10-24 19:10:35

抱歉,我才学两年,我也不会


by 高天宇 @ 2018-10-24 19:16:24

不给装弱者看题,这句话对吧。


by 求败 @ 2018-10-24 19:20:10

不给装弱者看题,这句话对吧。


by niolle @ 2018-10-24 19:24:04

不给装弱者看题,这句话对吧。


by 张鑫杰 @ 2018-10-24 19:26:39

@handsome·zlk ......


by 张鑫杰 @ 2018-10-24 19:27:33

我还是调不出来


by 张鑫杰 @ 2018-10-24 19:43:06

....


by 在想Peach @ 2019-01-20 21:11:25

我信你个鬼,~~你这个糟老头子坏的很~~


by _xcc_ @ 2019-01-25 15:06:29

考古


|