O(n)95分哪里错了??类似于线性dp的做法

P6188 [NOI Online #1 入门组] 文具订购

yagyagyag @ 2020-03-08 09:43:37

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
int min(int a,int b,int c) {
    return min(a,min(b,c));
}
struct Ans {
    int a,b,c;
    int sum,min;
} f[N];
bool check(int x)
{
    if (x && (f[x].a || f[x].b || f[x].c)) return 1;
    if (x==0) return 1;
    return 0;
}
int main() {
    cin>>n;
    Ans t;
    for (int i=1; i<=n; i++) {
        if (i-3>=0 && check(i-3)) {
            t=f[i-3];
            if (min(t.a,t.b,t.c+1)>f[i].min) f[i].a=t.a,f[i].b=t.b,f[i].c=t.c+1,f[i].min=min(t.a,t.b,t.c+1),f[i].sum=t.a+t.b+t.c+1;
            else if (min(t.a,t.b,t.c+1)==f[i].min && t.a+t.b+t.c+1>f[i].sum)
                f[i].a=t.a,f[i].b=t.b,f[i].c=t.c+1,f[i].min=min(t.a,t.b,t.c+1),f[i].sum=t.a+t.b+t.c+1;
        }

        if (i-4>=0 && check(i-4)) {
            t=f[i-4];
            if (min(t.a,t.b+1,t.c)>f[i].min) f[i].a=t.a,f[i].b=t.b+1,f[i].c=t.c,f[i].min=min(t.a,t.b+1,t.c),f[i].sum=t.a+t.b+1+t.c;
            else if (min(t.a,t.b+1,t.c)==f[i].min && t.a+t.b+1+t.c>f[i].sum)
                f[i].a=t.a,f[i].b=t.b+1,f[i].c=t.c,f[i].min=min(t.a,t.b+1,t.c),f[i].sum=t.a+t.b+1+t.c;
        }

        if (i-7>=0 && check(i-7)) {
            t=f[i-7];
            if (min(t.a+1,t.b,t.c)>f[i].min) f[i].a=t.a+1,f[i].b=t.b,f[i].c=t.c,f[i].min=min(t.a+1,t.b,t.c),f[i].sum=t.a+1+t.b+t.c;
            else if (min(t.a+1,t.b,t.c)==f[i].min && t.a+1+t.b+t.c>f[i].sum)
                f[i].a=t.a+1,f[i].b=t.b,f[i].c=t.c,f[i].min=min(t.a+1,t.b,t.c),f[i].sum=t.a+1+t.b+t.c;
        }
    }
    if (f[n].a==0 && f[n].b==0 && f[n].c==0) cout<<-1<<endl;
    else cout<<f[n].a<<" "<<f[n].b<<" "<<f[n].c<<endl;
    return 0;
}

第一个点爆zero


by ♘GoldHookDream♞ @ 2020-03-08 09:45:12

n = 0,输出0 0 0


by Luban @ 2020-03-08 09:45:30

我也是

因为0的时候会输出-1,但答案是0 0 0

我是O(1)打表算法


by Luban @ 2020-03-08 09:45:55

@eason0511 这就很烦,希望CCF不会这样!


by fresh_boy @ 2020-03-08 09:47:27

@可爱小鲁班 n=0,不是放在n%14==0的时候特判就可以的么。。。。


by mot1ve @ 2020-03-08 09:49:18

@可爱小鲁班 我更惨 我以为至少这三种各买一种,我小于14的全输出的-1,80pts


by 低調 @ 2020-03-08 09:51:21

因第一个点输出-1而95的我,wtnl


by HeartBlock_Love @ 2020-03-08 09:51:32

@kuoluo03 我也是!!!


by Luban @ 2020-03-08 09:51:54

@唱歌的向日葵 我之前加了

if (n<3||n==5) { cout<<-1<<endl; return 0; }


by fresh_boy @ 2020-03-08 09:54:10

@kuoluo03 对对对我就是这么错的


by yagyagyag @ 2020-03-08 13:17:09

@eason0511 wc 吐血


|