最简单的记忆化搜索,题目有点问题,a, b, c中若既满足其中一个不大于0,又满足其中一个大于20,按前一种情况。
Code:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int w[21][21][21]; 4 5 int dfs(int a, int b, int c) { 6 if (a <= 0 || b <= 0 || c <= 0) return 1; 7 if (~w[a][b][c]) return w[a][b][c]; 8 if (a < b && b < c) return w[a][b][c] = dfs(a, b, c-1) + dfs(a, b-1, c-1) - dfs(a, b-1, c); 9 else return w[a][b][c] = dfs(a-1, b, c) + dfs(a-1, b-1, c) + dfs(a-1, b, c-1) - dfs(a-1, b-1, c-1); 10 } 11 12 int main() { 13 int a, b, c, ans; 14 memset(w, -1, sizeof(w)); 15 while(~scanf("%d%d%d", &a, &b, &c)) { 16 if (a == -1 && b == -1 && c == -1) break; 17 if (a <= 0 || b <= 0 || c <= 0) ans = 1; 18 else if (a > 20 || b > 20 || c > 20) ans = dfs(20, 20, 20); 19 else ans = dfs(a, b, c); 20 printf("w(%d, %d, %d) = %d ", a, b, c, ans); 21 } 22 23 return 0; 24 }