首页 > > 程序设计 > C/C++ >

hdu 5937 -- Equation(搜索)

2018-06-17 21:50:46来源：未知阅读 ()

题目链接

problem description

Little Ruins is a studious boy, recently he learned addition operation! He was rewarded some number bricks of

1

Input

First line contains an integer $T$

Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result.

Sample Input

3
1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2
0 3 3 0 3 0 0 0 0

Sample Output

Case #1: 2
Case #2: 6
Case #3: 2


题意：输入c[1]~c[9]分别表示1~9这些数字的个数，现在用这些数字构成等式x+y=z（x,y,z都是个位的数字），等式不能相同（1+2=3与2+1=3不同），求最多能都成多少个等式？

思路：先用结构体数组存储所用的等式，共36个，然后搜索就行。注意剪枝；

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int ans;
int c[10];
struct Node
{
    int x,y,z;
}a[40];

void init()
{
    int tot=1;
    for(int i=1;i<=8;i++)
    {
        for(int j=1;i+j<=9;j++)
        {
            a[tot].x=i;
            a[tot].y=j;
            a[tot].z=i+j;
            tot++;
        }
    }
}

void dfs(int i,int sum)
{
   if(i>=37) { ans=max(ans,sum); return ; }
   if(sum+36-i+1<=ans) return ;
   int x=a[i].x;
   int y=a[i].y;
   int z=a[i].z;
   if(c[x]>0&&c[y]>0&&c[z]>0)
   {
       c[x]--; c[y]--; c[z]--;
       if(c[x]>=0&&c[y]>=0&&c[z]>=0) dfs(i+1,sum+1);
       c[x]++; c[y]++; c[z]++;
   }
   dfs(i+1,sum);
}

int main()
{
    init();
    int T,Case=1; cin>>T;
    while(T--)
    {
       for(int i=1;i<=9;i++) scanf("%d",&c[i]);
       ans=0;
       dfs(1,0);
       printf("Case #%d: %d\n",Case++,ans);
    }
    return 0;
}