求助

P1464 Function

_zhaosihan_qwq_ @ 2024-12-01 09:05:06

#include<iostream>
using namespace std;
int a[2000]={0},b[2005]={0},c[2005]={0};
int w(int a,int b,int c){
    if(a<=0&&b<=0&&c<=0){
        return 1;
    }
    if(a>20&&b>20&&c>20){
        return w(20,20,20);
    }
    if(a<b&&b<c){
        return w(a,b,c-1)+w(a,b-1,c-1)+w(a,b-1,c);
    }
    else {
        return w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
    }
}
int main(){
    for(int i=0;a[i-1]!=-1&&b[i-1]!=-1&&c[i-1]!=-1;i++){
        if(a[i-1]==-1&&b[i-1]==-1&&c[i-1]==-1) return 0;
        cin>>a[i]>>b[i]>>c[i];
        cout<<"w("<<a[i]<<","<<b[i]<<","<<c[i]<<") "<<"= "<<w(a[i],b[i],c[i]);
    }
    return 0;
}

by qujunhao @ 2024-12-01 09:06:46

#include<iostream>
using namespace std;
int a[2000]={0},b[2005]={0},c[2005]={0};
int w(int a,int b,int c){
    if(a<=0&&b<=0&&c<=0){
        return 1;
    }
    if(a>20&&b>20&&c>20){
        return w(20,20,20);
    }
    if(a<b&&b<c){
        return w(a,b,c-1)+w(a,b-1,c-1)+w(a,b-1,c);
    }
    else {
        return w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
    }
}
int main(){
    for(int i=0;a[i-1]!=-1&&b[i-1]!=-1&&c[i-1]!=-1;i++){
        if(a[i-1]==-1&&b[i-1]==-1&&c[i-1]==-1) return 0;
        cin>>a[i]>>b[i]>>c[i];
        cout<<"w("<<a[i]<<","<<b[i]<<","<<c[i]<<") "<<"= "<<w(a[i],b[i],c[i]);
    }
    return 0;
}

by qujunhao @ 2024-12-01 09:07:09

#include<bits/stdc++.h>
using namespace std;
long long a,b,c;
long long d[22][22][22];
long long w(long long a,long long b,long long c){
    if(a<=0||b<=0||c<=0){
        return 1;
    }
    if(a>20||b>20||c>20){
        a=b=c=20;
    }
    if(d[a][b][c]){
        return d[a][b][c];
    }
    if(a<b&&b<c){
        return d[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    }
    return d[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
}
int main(){
    while(cin>>a>>b>>c){
        if(a==-1&&b==-1&&c==-1){
            break;
        }
        printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,w(a,b,c));
    }
    return 0;
}

by xhq_5206 @ 2024-12-01 09:11:33

@_zhaosihanqwq 你这样写没错,但是会TLE 为什么呢?应为有好多地方重复算了

比如说你有个地方递归到了w(a, b, c)然后你又有一个地方调用了w(a, b, c)(其中a,b,c是同一个数字)你的代码会重复算这个函数,从而超时

你可以放一个三维数组保存函数的结果,即每个A[a][b][c] = w(a, b, c)


by _zhaosihan_qwq_ @ 2024-12-01 09:13:12

@xhq_5206 太谢谢了,已A


by xhq_5206 @ 2024-12-01 09:13:21

前面这位网友就是这样做的 (虽然你我不希望你抄它的代码)


by _zhaosihan_qwq_ @ 2024-12-01 09:14:10

已关注,
此贴结


by _zhaosihan_qwq_ @ 2024-12-01 09:15:10

@xhq_5206 额,他是我童鞋


by qujunhao @ 2024-12-01 09:16:38

@_zhaosihanqwq 什么同学


by duyuchen20204 @ 2024-12-01 09:17:11

666


|