uva 129 Krypton Factor （DFS+巧妙的判断方法）

本文主要是介绍uva 129 Krypton Factor （DFS+巧妙的判断方法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：

UVA  129

参考刘汝佳书《算法竞赛入门经典（第二版）》P195.

我是搬运工。

1.记录字母到‘A’的差值。

2.由于前面的子串已经判断过，所以只需判断含有新加字符的所有后缀子串。

3.注意输出格式

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;const int MAXN=80+5;
int s[MAXN];
int cnt;
int n,l;bool DFS(int pos)
{if(cnt++==n)//cnt代表第几小的困难的串{for(int i=0;i<pos;i++){printf("%c",'A'+s[i]);if(i==63&&i!=pos-1)printf("\n");else if(i%4==3&&i!=pos-1)printf(" ");}printf("\n%d\n",pos);return false;}for(int i=0;i<l;i++){s[pos]=i;bool q=true;for(int j=1;j*2<=pos+1;j++)//一共有pos+1个字符{bool p=false;for(int k=0;k<j;k++){if(s[pos-k]!=s[pos-k-j]){p=true;break;}}if(!p){q=false;break;}}if(q){if(!DFS(pos+1))return false;}}return true;
}int main()
{while(scanf("%d%d",&n,&l)!=EOF&&(n&&l)){memset(s,0,sizeof(s));cnt=0;DFS(0);}return 0;
}

这篇关于uva 129 Krypton Factor （DFS+巧妙的判断方法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---