题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1015
题目罗嗦了半天,其实意思很简单,就是给定一个目标值target,再给你一个备选字符串(5~12个字符),要你在这个字符串里选5个出来,满足题中给定的等式,并且你选择的这5个字符组成的字符串必须是所有可能情况中按字典序最大的情况。
简单分析下就可以看出,就是一个组合问题,问题解的最大规模就是12取5,就是12*11*10*9*8*7,而最小规模是5取5,所以应该用枚举法就可以搞定。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool isOk(int v,int w,int x,int y,int z,long int target)
{//判断是否符合要求
if((v-w*w+x*x*x-y*y*y*y+z*z*z*z*z)==target)
return true;
else
return false;
}
int charToInt(char ch)
{
return ch-'A'+1;
}
void mySort(string& p,int len)
{//让字符串按字母逆序排列,这样就可以很快找到最大符合要求的情况
int i,j;
char temp;
for(i=0;i<len-1;i++)
{
for(j=0;j<len-i-1;j++)
{
if(p[j]<p[j+1])
{
temp=p[j];
p[j]=p[j+1];
p[j+1] = temp;
}
}
}
}
int main(int argc,char* argv[])
{
long int target;
int tv,tw,tx,ty,tz;
string strTmp;
START:
while(cin>>target>>strTmp&&!(target==0&&strTmp=="END"))
{
int len = strTmp.length();
mySort(strTmp,len);
int v,w,x,y,z;
//下面开始用枚举法检验可能性,各个字符不能取同一个位置
for(v=0;v<len;++v)
{
for(w=0;w<len;++w)
{
if(v!=w)
{
for(x=0;x<len;++x)
{
if(x!=v&&x!=w)
{
for(y=0;y<len;++y)
{
if(y!=v&&y!=w&&y!=x)
{
for(z=0;z<len;++z)
{
if(z!=v&&z!=w&&z!=x&&z!=y)
{
tv = charToInt(strTmp[v]);
tw = charToInt(strTmp[w]);
tx = charToInt(strTmp[x]);
ty = charToInt(strTmp[y]);
tz = charToInt(strTmp[z]);
if(isOk(tv,tw,tx,ty,tz,target))
{
cout<<strTmp[v]<<strTmp[w]<<strTmp[x]<<strTmp[y]<<strTmp[z]<<endl;
goto START;//遇到最大的符合要求的值,直接跳出,进入下一个
}
}
}
}
}
}
}
}
}
}
cout<<"no solution"<<endl;
}
return 0;
}
本文转自Phinecos(洞庭散人)博客园博客,原文链接:http://www.cnblogs.com/phinecos/archive/2007/12/30/1021042.html,如需转载请自行联系原作者