一开始还在纠结怎么表示一个状态，毕竟是一个串。后来搜了一下题解发现了这里用一个整数的前12位表示转态就好了 ，1~o，0~'-'，每个状态用一个数来表示，然后dp写起来就比较方便了。
代码：
1 #include <iostream> 2 #include <sstream> 3 #include <cstdio> 4 #include <climits> 5 #include <cstring> 6 #include <cstdlib> 7 #include <string> 8 #include <cmath> 9 #include <vector> 10 #include <queue> 11 #include <algorithm> 12 #define esp 1e-6 13 #define pb push_back 14 #define in freopen("in.txt", "r", stdin); 15 #define out freopen("out.txt", "w", stdout); 16 #define print(a) printf("%d ",(a)); 17 #define bug puts("********))))))"); 18 #define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++) 19 #define inf 0x0f0f0f0f 20 using namespace std; 21 typedef long long LL; 22 typedef vector<int> VI; 23 typedef pair<int, int> pii; 24 typedef vector<pii,int> VII; 25 typedef vector<int>:: iterator IT; 26 #define N 50000 27 int dp[N]; 28 int ans; 29 void f(int x) 30 { 31 if(dp[x]) 32 return ; 33 int num = 0; 34 for(int i = 0; i < 12; i++) 35 if(x&(1<<i)) 36 num++; 37 ans = min(ans, num); 38 dp[x] = 1; 39 for(int i = 0; i <= 9; i++) 40 if(((x&(1<<i)) && (x&(1<<(i+1))) && !(x&(1<<(i+2)))) 41 ||(!(x&(1<<i)) && (x&(1<<(i+1))) && (x&(1<<(i+2))))) 42 f(x^(1<<(i+1))^(1<<i)^(1<<(i+2))); 43 } 44 int main(void) 45 { 46 47 char s[100]; 48 int T, t; 49 for(t = scanf("%d", &T), gets(s); t <= T; t++) 50 { 51 memset(dp, 0, sizeof(dp)); 52 gets(s); 53 int n = 0; 54 ans = 20; 55 for(int i = 0; i < 12; i++) 56 if(s[i] - '-') 57 n ^= (1<<i); 58 f(n); 59 printf("%d ", ans); 60 } 61 return 0; 62 }
或者可以用map+string的方法，一直都没怎么学过STL,看了http://www.myexception.cn/ai/1243266.html 这里的方法表示又涨了不少知识，拿来重新写了一遍（其实还是“剽窃”，没办法先当一个"搬运工”吧）。
1 #include <iostream> 2 #include <sstream> 3 #include <cstdio> 4 #include <climits> 5 #include <cstring> 6 #include <cstdlib> 7 #include <string> 8 #include <cmath> 9 #include <stack> 10 #include <map> 11 #include <vector> 12 #include <queue> 13 #include <algorithm> 14 #define esp 1e-6 15 #define pb push_back 16 #define in freopen("in.txt", "r", stdin); 17 #define out freopen("out.txt", "w", stdout); 18 #define print(a) printf("%d ",(a)); 19 #define bug puts("********))))))"); 20 #define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++) 21 #define inf 0x0f0f0f0f 22 using namespace std; 23 typedef long long LL; 24 typedef vector<int> VI; 25 typedef pair<int, int> pii; 26 typedef vector<pii,int> VII; 27 typedef vector<int>:: iterator IT; 28 map<string, bool> my; 29 int ans; 30 void dfs(string cur) 31 { 32 if(my.find(cur) != my.end()) 33 return; 34 int len = cur.size(), num = 0; 35 for(int i = 0; i < len; i++) 36 if(cur[i] == 'o') 37 num++; 38 ans = min(ans, num); 39 my[cur] = true; 40 for(int i = 0; i <= 9; i++) 41 { 42 if(cur.substr(i, 3) == "-oo") 43 { 44 string temp = cur; 45 temp.replace(i, 3, "o--"); 46 dfs(temp); 47 } 48 if(cur.substr(i, 3) == "oo-") 49 { 50 string temp = cur; 51 temp.replace(i, 3, "--o"); 52 dfs(temp); 53 } 54 } 55 } 56 int main(void) 57 { 58 int T; 59 string s; 60 for(int t = scanf("%d", &T); t <= T; t++) 61 { 62 cin>>s; 63 my.clear(); 64 ans = 20; 65 dfs(s); 66 printf("%d ", ans); 67 } 68 return 0; 69 }