hdu 5937 -- Equation(搜索)

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

新老客户大回馈,云服务器低至5折

题目链接

 

problem description

Little Ruins is a studious boy, recently he learned addition operation! He was rewarded some number bricks of 11 to 99 and infinity bricks of addition mark '+' and equal mark '='

Now little Ruins is puzzled by those bricks because he wants to put those bricks into as many different addition equations form x+y=zx+y=z as possible. Each brick can be used at most once and x, y, z are one digit integer. 

As Ruins is a beginer of addition operation, xx, yy and zz will be single digit number. 

Two addition equations are different if any number of xx, yy and zz is different. 

Please help little Ruins to calculate the maximum number of different addition equations.

Input

First line contains an integer TT, which indicates the number of test cases. 

Every test case contains one line with nine integers, the ithith integer indicates the number of bricks of ii. 

Limits 
1T30 
0bricks number of each type100

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;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:二分答案 ①

下一篇:(C++学习)关于CString的一些疑问