欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}