开始没注意空格全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;
}