Hdu1015&&寒假作业第二组I题

题意是A-Z对应1-26，然后给个目标数字和字符串，看看字符串里的某5个字符的组合能不能使v - w^2 + x^3 - y^4 + z^5 = target等式成立，其实多写几个循环也可以达到目的，不过应该会超时，所以还是dfs。

result数组保存最后5个数字，注意要用sort先降序排序，sort默认升序，得加个compare函数，因为本题可能有多解，人家要字典序最大的。num1数组是用来标记该数字被用过没有，注意要memset一下（忘了memset于是每次只能对一组数据也是醉了）。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <map>

#include <string>

#include <string.h>

#include <queue>

#include <vector>

using namespace std;

int pow(int x,int y)

{

    int z=;

    for(;y>;y--)

        z*=x;

    return z;

}

bool compare(int a,int b)

{

      return a>b;

}

int num[]={};

int num1[]={};

int result[]={};

char word[];

int tar;

int len;

int dfs(int m,int sum)

{

        if(sum==tar&&m==)

        return ;

        else if(sum!=tar&&m==)

          return ;

        else if(m<=)

        {

               for(int i=;i<len;i++)

               {

                       if(!num1[i])

                       {

                          num1[i]=;

                          result[m]=num[i];

                          if(m%==)

                           {

                                if(dfs(m+,sum-pow(num[i],m)))

                                return ;}

                          else {

                                if(dfs(m+,sum+pow(num[i],m)))

                                return ;}

                           num1[i]=;

                       }

               }

        }

        return ;

}

int main()

{

      while(scanf("%d%s",&tar,word)!=EOF)

      {

        memset(num1,,sizeof(num1));

        if(!strcmp(word,"END"))

                break;

        len=strlen(word);

        for(int i=;i<len;i++)

        {

              num[i]=word[i]-'A'+;

        }

        sort(num,num+len,compare);

                if(dfs(,))

                {

                        for(int i=;i<;i++)

                          printf("%c",result[i]+'A'-);

                          printf("\n");

                }

                else printf("no solution\n");

      }

      return ;

}

巴特西

Hdu1015&&寒假作业第二组I题

最新文章

热门文章