1 条题解

  • 1
    @ 2026-4-13 21:03:06

    本题题面简单易懂,很容易就能跟着题意模拟w函数

    //flpar
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define rg register
    #define PII pair<int,int>
    void init();
    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 a,b,c;
    signed main(){	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	while(cin>>a>>b>>c){
    		if(a==-1&&b==-1&&c==-1)
    			break;
    		cout<<w(a,b,c)<<'\n';
    	}
    	return 0;
    }
    void init(){
      return ;
    }
    

    但显然,仅仅通过模拟是无法通过此题的,在一些特定的三元组{a,b,ca,b,c}中,函数调用的深度过大,导致TLE,这时我们想到记忆化处理。

    //flpar
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define rg register
    #define PII pair<int,int>
    const int N=21;
    void init();
    int dp[N][N][N];
    int w(int a,int b,int c){
    	if(dp[a][b][c])
    		return dp[a][b][c];
    	if(a<=0||b<=0||c<=0)
    		return dp[a][b][c]=1;
    	if(a>20||b>20||c>20)
    		return dp[a][b][c]=w(20,20,20);
    	if(a<b&&b<c)
    		return dp[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)+w(a,b-1,c);
    	return dp[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 a,b,c;
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //	init();
    	while(cin>>a>>b>>c){
    		if(a==-1&&b==-1&&c==-1)
    			break;
    		cout<<w(a,b,c)<<'\n';
    	}
    	return 0;
    }
    void init(){
    	
    	return ;
    }
    

    但我们发现,即使记忆化了,但还是会RE,这是为什么呢?因为函数在递归的时候栈溢出了,我们进行一个简单的预处理,用三个for循环嵌套计算每一个w(a,b,c),时间复杂度为O(213)O(21^3),可记为O(1)O(1),这时对于每一个三元组{a,b,ca,b,c},输出dp[a][b][c],时间复杂度O(1),执行T次,总体时间复杂度O(T)O(T)

    //flpar
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define rg register
    #define PII pair<int,int>
    const int N=21;
    int dp[N][N][N];
    void init();
    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(dp[a][b][c])
    		return dp[a][b][c];
    	int res;
    	if(a<b&&b<c)
    		res=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    	else
    		res=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 dp[a][b][c]=res;
    }
    int a,b,c;
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	init();
    	while(cin>>a>>b>>c){
    		if(a==-1&&b==-1&&c==-1)
    			break;
    		cout<<w(a,b,c)<<'\n';
    	}
    	return 0;
    }
    void init(){
    	for(rg int i=0;i<=20;i++)
    		for(rg int j=0;j<=20;j++)
    			for(rg int k=0;k<=20;k++)
    				w(i,j,k);
    }
    

    信息

    ID
    220
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    11
    已通过
    2
    上传者