萌新求助:WA 4 5 8
查看原帖
萌新求助:WA 4 5 8
194093
天梦楼主2021/6/29 11:40

不知道为什么 WA ,求助大佬

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define int long long
#define uint unsigned int
#define ull unsigned long long
#define N 210000
#define M 70
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n,m,c,d,a[N],f[M][100000],sum[N],g[M][100000];
int q[N],l,r;

inline int get_posi(int id,int jd){
    return id*c+(jd-id);
}

inline void prework(){
    n++;
    for(int i=1;i<=n*c+m;i++) sum[i]=a[i]+sum[i-1];
    for(int i=1;i<=d;i++) f[0][i]=sum[i];
}

inline int compeat(int id,int k){
    return f[id-1][k]-sum[get_posi(id-1,k)];
}

inline void print(int id,int jd){
    if(g[id][jd]==0) return;
    print(id-1,g[id][jd]);
    printf("%lld ",get_posi(id-1,g[id][jd])-c+1);
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(m);read(c);read(d);
    // the goal is g[n][m]
    for(int i=1;i<=n*c+m;i++) read(a[i]);
    prework();
    for(int i=1;i<=n;i++){
        l=r=0;q[++r]=0;
        for(int j=0;j<=n+m;j++){
            while(l<r&&q[l+1]<j-d-1) l++;
            if(j>=i&&l<r){
                int k=q[l+1];
                // printf("i:%d j:%d k:%d\n",i,j,k);
                int now=get_posi(i,j),last=get_posi(i-1,k);
                f[i][j]=f[i-1][k]-sum[last]+sum[now-c+1];
                g[i][j]=k;
            }
            // else if(j>=i) printf("i:%d j:%d NOOOOOO\n",i,j);
            while(l<r&&compeat(i,q[r])<compeat(i,j)) r--;
            q[++r]=j;
        }
    }
    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=n+m;j++){
    //         printf("i:%d j:%d f[i][j]:%d posi:%d\n",i,j,f[i][j],get_posi(i,j));
    //     }
    // }
    printf("%lld\n",f[n][n+m]);
    print(n,n+m);
    return 0;
}

其中 fi,jf_{i,j} 表示的是抽了 jj 次,有 ii 次是连抽,且强制最后一次抽为连抽

2021/6/29 11:40
加载中...