HDU 1015 Safecracker (DFS)

时间:2022-06-02 14:57:19

题意:给一个数字n(n<=12000000)和一个字符串s(s<=17),字符串的全是有大写字母组成,字母的大小按照字母表的顺序,比如(A=1,B=2,......Z=26),从该字符串中选出5个字母,使得满足一下条件

v - w^2 + x^3 - y^4 + z^5 = n;

满足条件的可能有多组,请输出字典序最大的一组;

问题 :首先怎么找到满足条件的一组,一组字符串,对于每一个字符我们有两种选择 选||不选 ,然后在对每一个字符去进行这样的判断,然后把我们选好的5个字母在判断是否满足条件,但是这是你又会发现另外一个问题,就是它的解可能不是按照的字符串的顺序,这是我们就要想另外一种方法了,用一个vis[]数组标记每个字母,在用dfs去搜

其次是怎么输出字典序最大的呢,先对字符串进行排序,以从大到小排序,在找的过程中只要找到符合条件的一组就return;

AC代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 25;
int vis[maxn], n, a[maxn],b[maxn], k;
char ch[maxn], d[maxn];
bool flag; bool cmp(char p, char q) {
return p > q;
}
//v - w^2 + x^3 - y^4 + z^5 = target
void check() {
if (n == b[0] - b[1] * b[1] + b[2] * b[2] * b[2] - b[3] * b[3] * b[3] * b[3] + b[4] * b[4] * b[4] * b[4] * b[4]) {
flag = true;
}
return;
} void dfs(int num) {
if (flag) return;
if (num == 5) {
check();
return;
}
for (int i = 0; i < k; i++) {
if (!vis[i] && !flag) {
vis[i] = 1;
b[num] = a[i];
dfs(num + 1);
vis[i] = 0;
}
}
} int main() {
while (cin >> n >> ch && n && ch != "END") {
memset(vis, 0, sizeof(vis));
k = strlen(ch);
sort(ch, ch + k, cmp);
for (int i = 0; i < k; i++) {
a[i] = ch[i] - 'A' + 1;
}
flag = false;
dfs(0);
if (flag) {
for (int i = 0; i < 5; i++) {
d[i] = b[i] - 1 + 'A';
printf("%c", d[i]);
}
cout << endl;
}
else cout << "no solution" << endl;
}
}