poj 1020 Anniversary Cake

Anniversary Cake

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 19825		Accepted: 6505

Description

Nahid Khaleh decides to invite the kids of the "Shahr-e Ghashang" to her wedding anniversary. She wants to prepare a square-shaped chocolate cake with known size. She asks each invited person to determine the size of the piece of cake that he/she wants (which should also be square-shaped). She knows that Mr. Kavoosi would not bear any wasting of the cake. She wants to know whether she can make a square cake with that size that serves everybody exactly with the requested size, and without any waste.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by input data for each test case. Each test case consist of a single line containing an integer s, the side of the cake, followed by an integer n (1 ≤ n ≤ 16), the number of cake pieces, followed by n integers (in the range 1..10) specifying the side of each piece.

Output

There should be one output line per test case containing one of the words KHOOOOB! or HUTUTU! depending on whether the cake can be cut into pieces of specified size without any waste or not.

Sample Input

2
4 8 1 1 1 1 1 3 1 1
5 6 3 3 2 1 1 1

Sample Output

KHOOOOB!
HUTUTU!

周年纪念日的蛋糕

描述

Nahid Khaleh决定邀请“Shahr-e Ghashang”的孩子们参加她的结婚纪念日。她想准备一个已知大小的方形巧克力蛋糕。她要求每个被邀请的人确定他/她想要的那块蛋糕的大小(也应该是方形的)。她知道卡沃西先生不会容忍任何浪费蛋糕的行为。她想知道她是否能做一个方形蛋糕，大小和每个人要求的大小完全一致，而且没有任何浪费。

输入

输入文件的第一行包含一个整数t(1≤t≤10)，测试用例的数量，然后是每个测试用例的输入数据。每个测试用例包含一行，其中包含一个整数s，蛋糕的一面，后面跟着一个整数n(1≤n≤16)，蛋糕块的数量，后面跟着n个整数(范围是1..10)，指定每一块的一面。

输出

每个测试用例应该有一个输出行，其中包含单词KHOOOOB!或HUTUTU !这取决于蛋糕是否可以切成一定大小而不会有任何浪费。

Sample Input

2
4 8 1 1 1 1 1 3 1 1
5 6 3 3 2 1 1 1

Sample Output

KHOOOOB!
HUTUTU!


题意：先给出大方阵的边长，再给出m个小方阵并给出每个方阵的边长，问是否可以不发生重叠地把小方阵放进大方阵中，并且大方阵完全利用没有剩余
这题的代码不难写，关键是要找到策略，这题的策略比搜索本身的剪枝更有价值
摆放小方阵的策略是，尽可能往上面摆，然后尽可能往左边摆。另外有个策略一开始想错了，我是想先把小方阵排序，先放好大的，再放好小的，这样在摆放过程中可能出问题，画图可知，正确的策略是就目前的摆放情况，能放得到下哪个就放哪个，无所谓大小
 
为了满足尽可能放在左上方的条件，需要记录大方针的状态
col[i]的意义是，第i列，从最顶部数下来，被连续占据了多少格
注意在整个摆放过程中，每一列都保证是被连续占据的，不会出现断开的情况，这要求在搜索剪枝的时候处理好

代码：
#include 
#include 
#include 
using namespace std;
#define N 55
#define M 15

int n,m;
int col[N],s[M];

bool dfs(int mm)
{
    if(mm >= m) return true;

    int Min = N , c = 0;
    for(int i=1; i<=n; i++)
        if(col[i] < Min)
        {
            Min = col[i];
            c = i;
        }

    for(int i=1; i<=10; i++)
        if(s[i])
        {
            bool ok = true;
            if( !(c+i-1 <= n && col[c]+i <= n) ) continue;
            for(int k = c; k <= c+i-1; k++)
                if(col[k] != col[c])
                { 
                    ok = false; 
                    break; 
                }
            if(!ok) continue;
            
            s[i]--;
            for(int k=c; k <= c+i-1; k++)
                col[k] += i;
            if(dfs(mm+1)) return true;
            s[i]++;
            for(int k=c; k <= c+i-1; k++)
                col[k] -= i;
        }

    return false;
}

int main()
{
    int cas;
    cin >> cas;
    while(cas--)
    {
        int x,sum = 0;
        cin >> n >> m;
        memset(s,0,sizeof(s));
        for(int i=0; i        {
            cin >> x;
            s[x]++;
            sum += x * x;
        }
        memset(col,0,sizeof(col));
        if(sum != n * n || !dfs(0)) cout << "HUTUTU!" << endl;
        else                        cout << "KHOOOOB!" << endl;
    }
    return 0;
}