首页 > 代码库 > UVa129 Krypton Factor (回溯法)
UVa129 Krypton Factor (回溯法)
链接：http://acm.hust.edu.cn/vjudge/problem/19665
分析：cnt用于统计困难串个数，以串的各个位置为状态DFS，由于要字典序第k小，所以枚举cur位置上的字符时要从小到大，每次DFS考虑当前串的后缀是否有困难串，找到一个困难串则cnt++然后继续递归枚举、回溯，如果找到第k个后打印输出最后一波return。
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 int n, L, cnt, S[100]; 6 bool dfs(int cur) { 7 if (cnt == n) { 8 for (int i = 0; i < cur; i++) { 9 if (i % 64 == 0 && i > 0) cout << endl;10 else if (i % 4 == 0 && i > 0) cout << " ";11 cout << (char)(S[i] + ‘A‘);12 }13 cout << endl << cur << endl;14 return true;15 }16 for (int i = 0; i < L; i++) {17 S[cur] = i;18 bool ok = true;19 for (int j = 1; j * 2 <= cur + 1; j++) {20 bool equal = true;21 for (int k = 0; k < j; k++)22 if (S[cur - k] != S[cur - k - j]) {23 equal = false;24 break;25 }26 if (equal) { ok = false; break; }27 }28 if (ok) {29 cnt++;30 if (dfs(cur + 1)) return true;31 }32 }33 return false;34 }35 36 int main() {37 while (cin >> n >> L && (n || L)) {38 cnt = 0;39 dfs(0);40 }41 return 0;42 }
UVa129 Krypton Factor (回溯法)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。