XTOJ 1168 Alice and Bob （记忆化搜索）

本文主要是介绍XTOJ 1168 Alice and Bob （记忆化搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

OJ题目 ： click here ~~

题意分析：给一个数n，Alice可取1，2 ， 4 ……2的i次方 ，Bob可取1，3，9……3的i次方。Alice先取，后Bob。轮流来，每个人至少取1。求n变成0，至少需要取多少次。记忆化搜索 = 搜索 + dp 。

AC_CODE

#define gril 0
#define boy 1using namespace std;
const int inf = 100000000;
int A[20] , B[20];
int dp[10002][2];bool Find(int n , int who)
{if(who == gril){for(int i = 0;i <= 14;i++)if(n == A[i]) return true;return false;}if(who == boy){for(int i = 0;i <= 9;i++)if(n == B[i]) return true;return false;}
}int dfs(int n , int who)
{if(dp[n][who] != inf) return dp[n][who];//已经计算过，直接返回if(who == gril)//判断此轮为男生还是女生，若为女生{if(Find(n , gril))return dp[n][gril] = 1;else{for(int i = 0;n - A[i] >=0 ;i++)dp[n][gril] = Min(dp[n][gril] , dfs(n - A[i] , boy) + 1);return dp[n][gril];}}if(who == boy)//若为男生{if(Find(n , boy))return dp[n][boy] = 1;else{for(int i = 0;n - B[i] >= 0;i++)dp[n][boy] = Min(dp[n][boy] , dfs(n - B[i] , gril) + 1);return dp[n][boy];}}
}int main()
{int i , j ;j = 1;A[0] = j;for(i = 1;i <= 14;i++){j *= 2;A[i] = j;}j = 1;B[0] = j;for(i = 1;i <= 9;i++){j *= 3;B[i] = j;}int t;scanf("%d",&t);while(t--){for(int i = 0;i < 10002;i++)for(int j = 0;j < 2;j++)dp[i][j] = inf;int n;scanf("%d",&n);int ans = dfs(n , gril);printf("%d\n",ans);}return 0;
}

这篇关于XTOJ 1168 Alice and Bob （记忆化搜索）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---