UVA129 暴力dfs,有许多值得学习的代码

紫书195

题目大意:给一个困难的串,困难的串的定义就是里面没有重复的串。

思路:不需要重新对之前的串进行判重,只需要对当前的加入的字符进行改变即可。

因为是判断字典序第k个的字符串,所以要多一个全局变量cnt来记录目前是第几次循环到了。

 #include<bits/stdc++.h>

 using namespace std;
const int maxn = + ;
int n, L;
int s[maxn];
int cnt; bool dfs(int cur){
//printf("cur = %d\n", cur);
if (cnt++ == n){
for (int i = ; i < cur; i++){
if (i % == && i > ) printf("\n");
else if (i % == && i > ) printf(" ");
printf("%c", s[i] + 'A'); }
printf("\n");
printf("%d\n", cur);
return ;
}
else {
for (int i = ; i < L; i++){
s[cur] = i;
bool flag = true;
/*下面的这个暴力枚举半长的一定要学会*/
for (int j = ; j * <= cur + ; j++){/*必须cur+1,因为cur是从第0位开始的*/
int equa = ;
for (int k = ; k < j; k++){
if (s[cur - k] != s[cur - j - k]){
equa = ;
break;
}
}
if (equa == ) {flag = false; break;}
}
if (flag){
if (!dfs(cur + )) return false;
}
}
}
return ;
} int main(){
while (scanf("%d%d", &n, &L) && n + L != ){
cnt = ;
dfs();
}
return ;
}

关键:暴力dfs法不需要对之前已经确定的状态再次进行条件确定。 二分寻找合法串。  全局记录字典序的序列。

并且懂得暴力枚举一般的技巧

定义!!!!很重要。

目前如果我们放入的这个串合法的,那么二分j,那么对于cur-j和cur-j-k也必须要是合法的才行,所以这个是判断的条件,也是新手入门的难点

上一篇:UVA.839 Not so Mobile ( 二叉树 DFS)


下一篇:2018杭电多校第五场1002(暴力DFS【数位】,剪枝)