P1464 [PacNW 1999] Function

一、题目描述题目链接 P1464 [PacNW 1999] Function - 洛谷二、解题思路可以使用dfs记忆化搜索的方法来解决这个问题。通过阅读题目可知w(a,b,c)的最小值为1所以可以将memo数组初始化为0第三、四种情况时先查数组如果前面已经计算了就直接返回否则就递归计算然后更新memo[a][b][c]的值。三、代码实现#includebits/stdc.h using namespace std; long long memo[21][21][21] {0}; //记忆化搜索 long long w(long a,long b,long c){ if(a0||b0||c0) return 1; if(a20||b20||c20) return w(20,20,20); //如果前面计算过 if(memo[a][b][c]!0) return memo[a][b][c]; //如果没有计算过 else{ if(abbc){ memo[a][b][c] w(a,b,c-1)w(a,b-1,c-1)-w(a,b-1,c); return memo[a][b][c]; } else{ memo[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); return memo[a][b][c]; } } } int main(){ long long a,b,c; while(cinabc){ if(a-1b-1c-1) return 0; coutw(a, b, c) w(a,b,c)\n; } return 0; }