问题陈述:

  杭州电子科技大学HANGZHOU DIANZI UNIVERSITY Online Judge Problem - 1015

问题解析:

  深度优先搜索(Depth_First Search)

代码详解:  

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring> using namespace std; int flag, visited[]; int cmp(const void *a, const void *b){
return *(char *)b - *(char *)a;
} int calculate(char *ans) {
int res = , x = , sign = ;
for(int i=; i<; i++) {
for(int j=; j<=i; j++) {
x *= (ans[i] - 'A' + );
}
res += x * sign;
x = ;
sign *= (-);
}
return res;
} void dfs(char *str, int target, char *ans, int depth, int len) {
if(depth == ) {
if(calculate(ans) == target)
flag = ;
return;
}
for(int i=; i<len; i++) {
if(!visited[i]) {
ans[depth] = str[i];
visited[i] = ;
dfs(str, target, ans, depth+, len);
if(flag)
return;
visited[i] = ;
}
}
} int main()
{
int target;
char ans[], str[];
while(scanf("%d %s", &target, str)!=EOF && !(target== && strcmp(str, "END")==)) {
memset(visited, , sizeof(visited));
qsort(str, strlen(str), sizeof(char), cmp);
flag = ;
dfs(str, target, ans, , strlen(str));
if(flag){
ans[] = '\0';
puts(ans);
} else {
puts("no solution");
}
}
return ;
}

参考博客:CSDN Kizuki

转载请注明出处:http://www.cnblogs.com/michaelwong/p/4315092.html

05-11 21:47