100 但是Unaccepted

Sxu520 @ 2024-09-22 19:03:01

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[25][25][25]={0};
    long long b[100050][3]={0};
    int n1,n2,n3,j;
    for(int i=0;i<=20;i++){
        for(int j=0;j<=20;j++){
            for(int k=0;k<=20;k++){
                if(i==0||j==0||k==0)
                a[i][j][k]=1;
                else if(i<j&&j<k)
                a[i][j][k]=a[i][j][k-1]+a[i][j-1][k-1]-a[i][j-1][k];
                else
                a[i][j][k]=a[i-1][j][k]+a[i-1][j-1][k]+a[i-1][j][k-1]-a[i-1][j-1][k-1];
            }
        }
    }                                                 //记忆化把a[0][0][0]到a[20][20][20]都存进这个三维数组 
    for(j=0;;j++){
        cin>>n1>>n2>>n3;
        if(n1==-1&&n2==-1&&n3==-1)
        break;
        b[j][0]=n1;
        b[j][1]=n2;
        b[j][2]=n3;
    }                                                 //用二维数组b存要求的数
    for(int i=0;i<j;i++){
        if(b[i][0]<0||b[i][1]<0||b[i][2]<0)
        cout<<"w("<<b[i][0]<<", "<<b[i][1]<<", "<<b[i][2]<<") = "<<1<<endl;
        else if(b[i][0]>20||b[i][1]>20||b[i][2]>20)
        cout<<"w("<<b[i][0]<<", "<<b[i][1]<<", "<<b[i][2]<<") = "<<a[20][20][20]<<endl;
        else
        cout<<"w("<<b[i][0]<<", "<<b[i][1]<<", "<<b[i][2]<<") = "<<a[b[i][0]][b[i][1]][b[i][2]]<<endl;
    }                                                 /*若有某个数小于0输出1，若有某个数大于20输出a[20][20][20]
                                                      否则直接输出该组数据b[i][0]、b[i][1]、b[i][2]在a中对应的值*/
    return 0;
}

by yaoshuen @ 2024-09-22 19:15:34

@Sxu520 为啥非要写递推咧，个人建议递归+记忆化，递推代码又臭又长还难改

by yaoshuen @ 2024-09-22 19:16:21

AC code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
int p[22][22][22];
int w(int a,int b,int c){
    if(a<=0||b<=0||c<=0){
        return 1;
    }
    else if(p[a][b][c]!=0) return p[a][b][c];
    else if(a>20||b>20||c>20){
        p[a][b][c]=w(20,20,20);
    }
    else if(a<b&&b<c){
        p[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    }
    else p[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);
    return p[a][b][c];
}
signed main(){

    while(1){
        //memset(p,0,sizeof(p));
        scanf("%lld%lld%lld",&a,&b,&c);
        if(a==-1&&b==-1&&c==-1) break;
        printf("w(%lld, %lld, %lld) = ",a,b,c);
        a=(a>20?21:a);
        b=(b>20?21:b);
        c=(c>20?21:c);

        printf("%lld\n",w(a,b,c));
    }
    return 0;
}

by yaoshuen @ 2024-09-22 19:16:42

@Sxu520

by Sxu520 @ 2024-09-22 21:29:45

@yaoshuen 哦哦我明白了，递推的话会比递归和记忆化更久是这样吗

by Sxu520 @ 2024-09-22 21:33:10

@yaoshuen 可是RE不应该是因为超出数组范围吗，为啥我上边这个会RE啊

by yaoshuen @ 2024-09-23 17:53:17

不开long long见祖宗 @Sxu520

by yaoshuen @ 2024-09-23 17:53:35

给你改了

#include<bits/stdc++.h>

#define int long long
using namespace std;
int a[25][25][25]={0};
long long b[100050][3]={0};
int n1,n2,n3,j;
signed main(){

    for(int i=0;i<=20;i++){
        for(int j=0;j<=20;j++){
            for(int k=0;k<=20;k++){
                if(i==0||j==0||k==0)
                a[i][j][k]=1;
                else if(i<j&&j<k)
                a[i][j][k]=a[i][j][k-1]+a[i][j-1][k-1]-a[i][j-1][k];
                else
                a[i][j][k]=a[i-1][j][k]+a[i-1][j-1][k]+a[i-1][j][k-1]-a[i-1][j-1][k-1];
            }
        }
    }                                                 //记忆化把a[0][0][0]到a[20][20][20]都存进这个三维数组 
    for(j=0;;j++){
        cin>>n1>>n2>>n3;
        if(n1==-1&&n2==-1&&n3==-1)
        break;
        b[j][0]=n1;
        b[j][1]=n2;
        b[j][2]=n3;
    }                                                 //用二维数组b存要求的数
    for(int i=0;i<j;i++){
        if(b[i][0]<0||b[i][1]<0||b[i][2]<0)
        cout<<"w("<<b[i][0]<<", "<<b[i][1]<<", "<<b[i][2]<<") = "<<1<<endl;
        else if(b[i][0]>20||b[i][1]>20||b[i][2]>20)
        cout<<"w("<<b[i][0]<<", "<<b[i][1]<<", "<<b[i][2]<<") = "<<a[20][20][20]<<endl;
        else
        cout<<"w("<<b[i][0]<<", "<<b[i][1]<<", "<<b[i][2]<<") = "<<a[b[i][0]][b[i][1]][b[i][2]]<<endl;
    }                                                 /*若有某个数小于0输出1，若有某个数大于20输出a[20][20][20]
                                                      否则直接输出该组数据b[i][0]、b[i][1]、b[i][2]在a中对应的值*/
    return 0;
}

by yaoshuen @ 2024-09-23 17:53:52

@Sxu520

by Sxu520 @ 2024-09-24 12:37:33

@yaoshuen okok太谢谢了