P1464

Unknown_Accepted · 2024-06-08 11:31:14 · 题解

题目传送门

这道题怎么能没有 c++ 的递推呢？今天，我来给大家一份 c++ 写的递推题解。我为啥要用递推写呢？因为递归实在写不下去了。

进入正题

部分代码&精讲

首先，开头不用说：

#include<iostream>
#define int long long
using namespace std;
int p[21][21][21];

接下来，我们要来一波初始化：

for(int i=0;i<21;i++){
    for(int j=0;j<21;j++){
        p[0][i][j]=1;//只要有一个0就返回1
        p[i][0][j]=1;
        p[i][j][0]=1;
    }
}

下一步，把每个值打出来：

for(int a=1;a<21;a++){
    for(int b=1;b<21;b++){
        for(int c=1;c<21;c++){
                    //第一二条下一段代码处理
                if(a<b&&b<c){//第三条
                    p[a][b][c]=
                    p[a][b][c-1]
                    +p[a][b-1][c-1]
                    -p[a][b-1][c];
                }else{//第四条
                    p[a][b][c]=
                    p[a-1][b][c]
                    +p[a-1][b-1][c]
                    +p[a-1][b][c-1]
                    -p[a-1][b-1][c-1];
                }
            }
    }
}

最后这部分有一些坑，在注释里（码风不好求原谅）：

int a,b,c;
cin>>a>>b>>c;
for(;(a!=-1||b!=-1||c!=-1);cin>>a>>b>>c){
    int d=a,e=b,f=c;
    //重要的事情说三遍
    if(d<=0)d=0,e=0,f=0;//有一个是零就全是零!
    if(e<=0)d=0,e=0,f=0;//有一个是零就全是零!
    if(f<=0)d=0,e=0,f=0;//有一个是零就全是零!
    if(d>20||e>20||f>20){//有一个20就全是20
        d=e=f=20;
    }
    printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,p[d][e][f]);//注意格式
} 

完整代码

当当当当。

#include<iostream>
#define int long long
using namespace std;
int p[21][21][21];
signed main(){
    for(int i=0;i<21;i++){
        for(int j=0;j<21;j++){
            p[0][i][j]=1;
            p[i][0][j]=1;
            p[i][j][0]=1;
        }
    }
    for(int a=1;a<21;a++){
        for(int b=1;b<21;b++){
            for(int c=1;c<21;c++){
                if(a<b&&b<c){
                    p[a][b][c]=
                    p[a][b][c-1]
                    +p[a][b-1][c-1]
                    -p[a][b-1][c];
                }else{
                    p[a][b][c]=
                    p[a-1][b][c]
                    +p[a-1][b-1][c]
                    +p[a-1][b][c-1]
                    -p[a-1][b-1][c-1];
                }
            }
        }
    }
    int a,b,c;
    cin>>a>>b>>c;
    for(;(a!=-1||b!=-1||c!=-1);cin>>a>>b>>c){
        int d=a,e=b,f=c;
        if(d<=0)d=0,e=0,f=0;
        if(e<=0)d=0,e=0,f=0;
        if(f<=0)d=0,e=0,f=0;
        if(d>20||e>20||f>20){
            d=e=f=20;
        }
        printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,p[d][e][f]);
    } 
    return 0;
}