uva 10651 Pebble Solitaire（动态规划：记忆化搜索）

本文主要是介绍uva 10651 Pebble Solitaire（动态规划：记忆化搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意是对于当前的一行，求出转换到不能再转换状态所需的最多步数

题目看起来没有思路，感觉找不到状态转移方程

看了别人的题解才知道这个题还是很容易的

但是需要想到stl map

我们用dp[s]表示把s转换为不能转换所需的最多步数

如果可以由s转换到t

则有：dp[s] = max(dp[s], dp[t])

因为起始状态不好找，所以用记忆化搜索来写比较好

代码如下：

#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;string s, t;
map<string, int> dp;int dfs(string s) {if(dp[s]) return dp[s];dp[s] = 0;for(int i=0; i<10; ++i) {if(s[i]=='-' && s[i+1]=='o' && s[i+2]=='o') {t = s;t[i] = 'o'; t[i+1] = '-'; t[i+2] = '-';dp[s] = max(dp[s], dfs(t)+1);}if(s[i]=='o' && s[i+1]=='o' && s[i+2]=='-') {t = s;t[i] = '-'; t[i+1] = '-'; t[i+2] = 'o';dp[s] = max(dp[s], dfs(t)+1);}}return dp[s];
}int main(void) {int n, ans;scanf("%d", &n);while(n--) {cin >> s;ans = 0;for(int i=0; i<12; ++i)if(s[i] == 'o')++ans;printf("%d\n", ans-dfs(s));}return 0;
}

这篇关于uva 10651 Pebble Solitaire（动态规划：记忆化搜索）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---