uva 10651 - Pebble Solitaire(记忆化搜索）
题目链接：10651 - Pebble Solitaire
题目大意：给出一个12格的棋盘，‘o'代表摆放棋子，’-‘代表没有棋子， 当满足’-oo'时， 最右边的棋子可以跳到最左边的位子，而中间的棋子则被消除，‘o--'， 问对于一个给定了的棋盘，通过上述消除棋子的方法最后最少绳几个棋子在棋盘上。
解题思路：递归搜索 + 记忆化， 并且记忆化的值为所有测试数据公用的，也就是说在程序运行的开始初始化后，后面无需再进行清0。
#include <stdio.h>#include <string.h>const int N = 10000;const int M = 50;int rec[N];int change(char str[]) { int num = 0; for (int i = 0; i < 12; i++) {if (str[i] == 'o') num = num * 2 + 1;else num = num * 2; } return num;}int count(char str[]) { int cnt = 0; for (int i = 0; i < 12; i++)if (str[i] == 'o') cnt++; return cnt;}int dp(char str[]) { int now = change(str); if (rec[now] >= 0)return rec[now]; int& cnt = rec[now]; cnt = count(str); for (int i = 1; i < 11; i++) {if (str[i] == 'o') { if (str[i - 1] == 'o' && str[i + 1] == '-') {str[i - 1] = str[i] = '-', str[i + 1] = 'o';int cur = dp(str);str[i - 1] = str[i] = 'o', str[i + 1] = '-';if (cur < cnt) cnt = cur; } else if (str[i - 1] == '-' && str[i + 1] == 'o') {str[i - 1] = 'o', str[i] = str[i + 1] = '-';int cur = dp(str);str[i - 1] = '-', str[i] = str[i + 1] = 'o';if (cur < cnt) cnt = cur; }} } return cnt;}int main() { int cas; char str[M]; memset(rec, -1, sizeof(rec)); scanf("%d", &cas); while (cas--) {scanf("%s", str);printf("%d\n", dp(str)); } return 0;}