链接：http://codeforces.com/contest/962/problem/C
当时看到这个题目不敢写搜索，瞻前顾后，怕超时，一直想其他的办法，比赛结束后发现其实就是用搜索来写。
还是应该记住这个教训，以后看到题目不要总是瞻前顾后的，没有更好的方法的时候那就这么写就对了
否则自己更得不到提升，并且现在搜索都生疏了
题意：给你一个数N，你可以在其中删除几位，使剩下的数字组成一个新数是个平方数。
1 #include <cmath> 2 #include <string> 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 #include <algorithm> 7 8 using namespace std; 9 #define ll long long 10 const int INF = 0xffffff0; 11 12 char s[100]; 13 int len,flag; // len记录s长度,flag做标记 14 15 void dfs(int x,int val,int step) 16 { 17 int b = s[x]-'0'; 18 if(x == len-1) // 搜索到最后一位 19 { 20 int c = sqrt(val); 21 if(c*c == val && val != 0) //此时先不取用c[x] 22 { 23 flag = min(flag,step+1); // 因为不取用c[x]，所以相当于多删除了一个 24 } 25 val = val*10+b; // 取用c[x] 26 c = sqrt(val); 27 if(c*c == val && val != 0) 28 { 29 flag = min(flag,step); 30 } 31 return ; 32 } 33 34 if(val != 0 || b != 0) 35 { 36 dfs(x+1,val*10+b,step); 37 } 38 // if(b == 0 && val == 0) 39 dfs(x+1,val,step+1); // 此时写为dfs(x+1,val*10+b,step+1) 40 // 或者 dfs(x+1,val*10,step+1)是没有区别的 41 }; 42 43 int main() 44 { 45 cin >> s; 46 len = strlen(s); 47 flag = INF; 48 dfs(0,0,0); 49 if(flag == INF) // flag的值没有被更新，即没找到平方数 50 cout << "-1" << endl; 51 else 52 cout << flag << endl; 53 return 0; 54 }
自己推了一下递归，发现又把自己绕晕了，搜索又生疏了···