如何做到最快
查看原帖
如何做到最快
345837
空木秋人楼主2020/10/20 20:03

开始没注意空格全WA了,提交了好几次才反映过来,有点惨。进入正题


开启O2优化,第一次提交的时候没有使用 ios::sync_with_stdio(false); std::cin.tie(0); 13ms ac。后面加上了这两行结果15ms,我看到最快的好像11ms,如何优化呢?代码如下:

int w[21][21][21]={0};

//memorization
int fun(ll a, ll b, ll c){
    if(a<=0 || b<=0 || c<=0){
        return 1;
    }
    else if(a>20 || b>20 || c>20){
        return fun(20,20,20);
    }
    //if cached
    if(w[a][b][c])
        return w[a][b][c];
    //cache it
    if (a<b && b<c) {
        w[a][b][c]=fun(a,b,c-1) + fun(a,b-1,c-1) -fun(a,b-1,c);
    }
    else {
        w[a][b][c]=fun(a-1,b,c)+fun(a-1,b-1,c)+fun(a-1,b,c-1)-fun(a-1,b-1,c-1);
    }
    return w[a][b][c];
}

int main(){
    //关闭同步,解除绑定
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    ll a,b,c;
    while (cin>>a>>b>>c) {
        if(a==-1&&b==-1&&c==-1) break;
        cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<fun(a,b,c)<<endl;
        //printf("w(%lld, %lld, %lld) = %d\n",a,b,c,fun(a,b,c));
    }
    return 0;
}

2020/10/20 20:03
加载中...