16杭州ccpc Equation HDU - 5937（搜索）-白红宇

16杭州ccpc Equation HDU - 5937（搜索）

阅读量：4207 次

发布时间：2019-05-26

本文共 2044 字，大约阅读时间需要 6 分钟。

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

1 1 to

9 9 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=z x+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,

x x,

y y and

z z will be single digit number.

Two addition equations are different if any number of

x x,

y y and

z z is different.

Please help little Ruins to calculate the

maximum number of different addition equations.

Input

First line contains an integer

T T, which indicates the number of test cases.

Every test case contains one line with nine integers, the

ith ith integer indicates the number of bricks of

i i.

Limits

1≤T≤30 1≤T≤30

0≤bricks number of each type≤100 0≤bricks number of each type≤100

Output

For every test case, you should output

'Case #x: y', where

x indicates the case number and counts from

1and

y is the result.

Sample Input

31 1 1 1 1 1 1 1 12 2 2 2 2 2 2 2 20 3 3 0 3 0 0 0 0

Sample Output

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

题意：给出1~9这些数字的个数，现在用这些数字构成等式x+y=z（x,y,z都是个位的数字），等式不能相同（1+2=3与2+1=3不同），求最多能都成多少个等式？ 思路：先用结构体数组存储所用的等式，共36个，然后搜索就行。注意剪枝；

int num[10];struct node{    int x,y,z;}a[40];int ans;void dfs(int i,int sum){    if(i>36)    {        ans=max(ans,sum);        return ;    }    if(sum+36-i+1<=ans) return ;    int x=a[i].x,y=a[i].y,z=a[i].z;    if(num[x]>0 && num[y]>0 && num[z]>0)    {        num[x]--,num[y]--,num[z]--;        if(num[x]>=0 && num[y]>=0 && num[z]>=0)dfs(i+1,sum+1);        num[x]++,num[y]++,num[z]++;    }    dfs(i+1,sum);}int main(){    ios::sync_with_stdio(false);    for(int i=1,id=1;i<9;i++)        for(int j=1;j+i<=9;j++)            a[id].x=i,a[id].y=j,a[id++].z=i+j;    int T,cas=1;    cin>>T;    while(T--)    {        for(int i=1;i<10;i++)cin>>num[i];        ans=0;        dfs(1,0);        cout<<"Case #"<
    
     <<": "<
     
      <

转载地址：http://ieali.baihongyu.com/

你可能感兴趣的文章