洛谷P1464Function（逆向递推递归+记忆化）

题目链接：https://www.luogu.org/problemnew/show/P1464

分析和思路：

直接搜索超时，必须用数组记忆化一下

难点在于：怎样用三维数组保存结果。使之记忆化。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <vector>
 6 #include <map>
 7 #include <set>
 8 #include <stack>
 9 #include <queue>
10 #include <cstdio>
11 #include <cstring>
12 #include <cmath>
13 using namespace std;
14 typedef long long ll;
15 typedef unsigned long long ull;
16 const int maxn=101;
17 int vis[maxn];
18 struct px
19 {
20     ll f[maxn][maxn];
21 }F[maxn];
22 
23 ll w(ll a,ll b,ll c)
24 {
25     if(a<=0 || b<=0 || c<=0) return 1;
26     else if(a>20 || b>20 || c>20) return w(20,20,20);
27     else if(F[a].f[b][c]) return F[a].f[b][c];
28     else if(a<b && b<c) return F[a].f[b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
29     else return F[a].f[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);
30 }
31 
32 int main()
33 {
34     ios::sync_with_stdio(false); cin.tie(0);
35     
36     ll x,y,z;
37     for(;;)
38     {
39         cin>>x>>y>>z;
40         if(x==-1 && y==-1 && z==-1) break;
41         
42         ll ans=w(x,y,z);
43         
44         cout<<"w("<<x<<", "<<y<<", "<<z<<") = "<<ans<<endl;
45     } 
46     
47     return 0;    
48 }