1 条题解
-
1
本题题面简单易懂,很容易就能跟着题意模拟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 ; }但显然,仅仅通过模拟是无法通过此题的,在一些特定的三元组{}中,函数调用的深度过大,导致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),时间复杂度为,可记为,这时对于每一个三元组{},输出dp[a][b][c],时间复杂度O(1),执行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
- 上传者