Hduoj 1015【水題】

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char str[15];
int num, ok, s[15], vis[30], n, ans[5];
int cmp(const void *a, const void *b)
{
	return *(int *)b - *(int *)a;
}
int power(int x,int y)
{
	int i;
	i = x;
	while(--y)
	{
		x *= i;
	}
	return x;
}
void dfs()
{
	int i, j, k, l, m;
	for(i = 0; i < n; ++i)
	{
		vis[i] = 1;
		for(j = 0; j < n; ++j)
		{
			if(vis[j])
			continue;
			vis[j] = 1;
			for(k = 0; k < n; ++k)
			{
				if(vis[k])
				continue;
				vis[k] = 1;
				for(l = 0; l < n; ++l)
				{
					if(vis[l])
					continue;
					vis[l] = 1;
					for(m = 0; m < n; ++m)
					{
						if(vis[m])
						continue;
						if(s[i] - power(s[j], 2) + power(s[k], 3) - power(s[l], 4) + power(s[m], 5) == num)
						{
							ok = 1;
							ans[0] = s[i];
							ans[1] = s[j];
							ans[2] = s[k];
							ans[3] = s[l];
							ans[4] = s[m];
							return;
						}
					}
					vis[l] = 0;
				}
				vis[k] = 0;
			}
			vis[j] = 0;
		}
		vis[i] = 0;
	}
}
int main()
{
	int i, j, k;
	while(scanf("%d %s", &num, str) != EOF)
	{
		if(num == 0 && strcmp(str, "END") == 0)
		break;
		n = strlen(str);
		for(i = 0; i < n; ++i)
		s[i] = str[i] - 64;
		ok = 0;
		qsort(s, n, sizeof(s[0]), cmp);
		memset(vis, 0, sizeof(vis));
		dfs();
		if(ok)
		printf("%c%c%c%c%c
", ans[0]+64, ans[1]+64, ans[2]+64, ans[3]+64, ans[4]+64);
		else
		printf("no solution
");
	}
	return 0;
}

題意:5~12個の異なる大文字からなる文字列を与え、目標値を与え、A~Zの値を1~26と規定し、この文字列から5個の文字列vwxyzを選択して1つの文字列vwxyzを構成し、v-w^2+x^3-y^4+z^5=targetを要求する.要求に合致する文字列が複数ある場合は、辞書順が最も大きい文字列を出力します.そうでなければno solutionを出力します.
構想:この問題は直接暴力的に解くことができて、先に与えた文字列の値を配列の中に保存して、それから配列に対して降順の順序を行って、それから5つのfor循環はこの5つの文字を求めます.