HDU 1015 Safecracker （DFS）

题意：给一个数字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;

	}

}

巴特西

HDU 1015 Safecracker （DFS）

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

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

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

最新文章

热门文章