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 吐血