HDU 1331 Function Run Fun(记忆化搜索)
程序员文章站
2022-07-12 08:59:20
...
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1331
题意是输入三个数,然后按题目中的条件输出这三个数的值。
因为情况会有很多种,所以也会有重复出现的状态,所以需要用dp数组来标记一下。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 55
using namespace std;
int dp[maxn][maxn][maxn],n,m,p;
int dfs(int x,int y,int z){
if(x <= 0 || y <= 0 || z <= 0)return 1;
if(x > 20 || y > 20 || z > 20)return dfs(20,20,20);
if(dp[x][y][z])return dp[x][y][z]; // 如果这种状态被标记过,直接返回dp
if(x < y && y < z)return dp[x][y][z] = dfs(x,y,z-1) + dfs(x,y-1,z-1) - dfs(x,y-1,z);
return dp[x][y][z] = dfs(x-1,y,z) + dfs(x-1,y-1,z) + dfs(x-1,y,z-1) - dfs(x-1,y-1,z-1);
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&p)){
if(n == -1 && m == -1 && p == -1)break;
memset(dp,0,sizeof(dp));
int ans = dfs(n,m,p);
printf("w(%d, %d, %d) = %d\n",n,m,p,ans);
}
return 0;
}