题目

Description

Little Ruins is a studious boy, recently he learned addition operation! He was rewarded some number bricks of 1 to 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 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, y and z will be single digit number.

Two addition equations are different if any number of x, y and z is different.

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

Input

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

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

Limits
1≤T≤30
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 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

题解

{% cq %}
有技巧的暴力,就不算暴力了
{% endcq %}

历时超长的一道题,如果不是知道思路没问题,估计中途就想办法用其他方法了

题目的意思就是给任意数目的 1-9 9个数字,使尽可能多的凑 a+b=c 的式子
其中 a、b、c 必须是 1-9 的数字,并且 a+b=c 和 b+a=c 被看成是两个不同的式子

首先,很容易发现,总共只有 36 种选择,因此可以尝试使用搜索解决

不考虑时间,思路如下:
暴力 DFS 搜索,遍历所有的情况,判断所有情况中递归的最大深度
时间复杂度 O(2³⁶)

优化:
显然,这样写超时会非常严重

1. 对于遍历次数的优化
   仔细跟着思路模拟一下,会发现,对于 a+b=c 和 b+a=c 的情况,他们属于可以把 a+b=c 选择两次的情况
   而直接遍历 36 种可能显然把 a+b=c 只选一次的情况 遍历了两次
   因此,这里可以先标记下然后再进行判断,如果 a+b=c 不在 DFS 递归的栈里(已经遍历过只选一次的分支),那么不再遍历 b+a=c
2. 剪枝

• 当深度大于等于 36 的时候,显然已经找到答案了,可以直接返回
• 如果把现在所有的数字除以 3 (每个式子有 3 个数字) 再加上已经遍历的深度都不可能比已有答案大,显然可以直接返回
• 如果把当前已经遍历的深度(已选择的式子数目),和剩下能遍历的深度加起来都没有已有答案大,可以直接返回

3. 预处理
   预处理到每个深度,其以后所有式子需要的每个数字的个数.当发现数字足够时,直接返回返回答案

这样处理后,不管是数字总体比较少(直接爆搜也很快)还是数字数目比较多(由于数字数目多,所以预处理可以解决许多情况,并且剪枝可以进一步减少搜索量),都可以较快地搜到答案

对于这道题,其数据量处于爆搜能够解决的边缘范围,因此采用一定的搜索技巧可以达到时间要求
而搜索的技巧就是上面的三种
而其中剪枝分为 可行性剪枝 和 最优性剪枝

注释比较详细

代码

//#define debug
//#include <ctime>

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

int Left[37][10];
int lis[36][3];

//记录对应的等式是否在这支dfs树枝上
//0 (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8)
//7 (2,3) (2,4) (2,5) (2,6) (2,7) 
//12 (3,4) (3,5) (3,6)
//15 (4,5)
bool vis[16];
#define Flag(a,b) (vis[(8*(a-1)-(a-1)*(a-1))+(b-a-1)])

int num[10];
int deep;

void Debug(int n, int m) {
    return;
    for (int i = 0; i < n; i++)
        cout << " ";
    cout<<n<<" "<<lis[m][0]<<"+"<<lis[m][1]<<"="<<lis[m][2];
    cout<<"\t\t\t\t\t deep:"<<n<<" p:"<<m<<"\t";
    for(int i=1;i<=9;i++)
        cout<<num[i]<<" ";
    cout<<endl;
}

void dfs(int p, int d, int cnt) {
    // 剪枝
    if (d == 36 || deep ==36) return;// 不可能有更优情况
    if (cnt/3+d <= deep) return;// 所有数字全用上也无法最优  
    if (d+36-p <= deep) return;//剩下的组合都能用上都不可能更优

    //如果有预处理能解决的问题,直接返回答案
    bool Ok = true;
    for(int i=1;i<=9;i++){
        if(num[i] < Left[p][i]){
            Ok = false;
            break;
        }
    }
    if(Ok){
        deep = max(deep,d+36-p);
        return;
    }
    
    deep = max(d,deep);

    for (int i = p; i < 36; i++) {
        num[lis[i][0]]--;
        num[lis[i][1]]--;
        num[lis[i][2]]--;
        if (num[lis[i][0]]>=0 && num[lis[i][1]]>=0 && num[lis[i][2]]>=0){
            Debug(d + 1, i);
            if(lis[i][0] < lis[i][1]){
                Flag(lis[i][0],lis[i][1]) = true;
                dfs(i + 1, d + 1, cnt - 3);
                Flag(lis[i][0],lis[i][1]) = false;
            }else{
                if(lis[i][0] == lis[i][1] || 
                    (lis[i][0] > lis[i][1] && Flag(lis[i][1],lis[i][0]) == true)
                )
                    dfs(i + 1, d + 1, cnt - 3);
            }  
        }
        num[lis[i][0]]++;
        num[lis[i][1]]++;
        num[lis[i][2]]++;
    }
}

//预处理
void Pre(){
    //init 
    memset(vis,false,sizeof(vis));

    //预处理表
    int pos = 0;
    for(int i=1;i<=9;i++)
        for(int j=1;j<=9;j++)
            if(i+j<10){
                lis[pos][0] = i;
                lis[pos][1] = j;
                lis[pos++][2] = i+j;
            }else{
                break;
            }

    //预处理结果
    memset(Left[36],0,sizeof(Left[36]));
    for(int i=35;i>=0;i--){
        for(int j=1;j<=9;j++){
            Left[i][j] = Left[i+1][j];
        }
        for(int j=0;j<3;j++)
            Left[i][lis[i][j]]++;
    }

    //预处理显示
    /*
        cout<<"lis"<<endl;
        for(int i=0;i<pos;i++){
            cout<<i<<": "<<lis[i][0]<<" + "<<lis[i][1]<<" = "<<lis[i][2]<<endl;
        } 
        cout<<endl;
        cout<<"Left"<<endl;
        for(int i=0;i<pos;i++){
            cout<<i<<": ";
            for(int j=1;j<=9;j++)
                cout<<Left[i][j]<<" ";
            cout<<endl;
        }
        cout<<"==============="<<endl;
    //*/
}

int main() {
    #ifdef debug
    freopen("in.txt", "r", stdin);
    int START = clock();
    #endif

    cin.tie(0);
    cin.sync_with_stdio(false);

    Pre();

    int T;
    cin >> T;
    for (int kase = 1; kase <= T; kase++) {
        int cnt = 0;
        for (int i = 1; i <= 9; i++) {
            cin >> num[i];
            num[i]=min(num[i],17-i);
            cnt += num[i];
        }
        deep = 0;
        dfs(0, 0, cnt);
        cout << "Case #" << kase << ": " << deep << endl;
    }

    #ifdef debug
    printf("Time:%.3lfs\n", double(clock() - START) / CLOCKS_PER_SEC);
    #endif

    return 0;
}