poj - 1020 - Anniversary Cake

題意：給出n個小正方形，問能否將這n個小正方形拼成一個邊長為s的大正方形（不可重疊，不可留空）(小正方形的邊長[1, 10], 1 <= n <= 16)
 

——>>好題，好題，題意是如此的平常，卻不容易做……

在小正方形的面積和 == 大正方形的面積的前提下，每次先填最凹的地方，看能否能填完n個小正方形。

[cpp] #include <cstdio>  
#include <cstring>  
 
using namespace std; 
 
const int maxn = 40 + 10; 
const int maxm = 10 + 10; 
int s, n, num[maxm], side[maxn]; 
bool ok; 
 
void dfs(int cur) 
{ 
    if(ok) return; 
    if(cur == n) 
    { 
        ok = 1; 
        return; 
    } 
 
    int min_col = 1, i, j;     //找最凹處  
    for(i = 2; i <= s; i++) 
        if(side[i] < side[min_col]) 
            min_col = i; 
 
    int border = s + 1;     //最凹處右界  
    for(i = min_col + 1; i <= s; i++) 
        if(side[i] != side[min_col]) 
        { 
            border = i; 
            break; 
        } 
 
    for(i = 10; i >= 1; i--) 
    { 
        if(num[i] > 0 && i <= s - side[min_col] && i <= border - min_col) 
        { 
            for(j = min_col; j < min_col + i; j++) side[j] += i; 
            num[i]--; 
            dfs(cur + 1); 
            num[i]++; 
            for(j = min_col; j < min_col + i; j++) side[j] -= i; 
        } 
    } 
} 
 
int main() 
{ 
    int t, temp, sum, i; 
    scanf("%d", &t); 
    while(t--) 
    { 
        sum = 0; 
        memset(num, 0, sizeof(num)); 
        memset(side, 0, sizeof(side)); 
        scanf("%d%d", &s, &n); 
        for(i = 0; i < n; i++) 
        { 
            scanf("%d", &temp); 
            num[temp]++; 
            sum += temp * temp; 
        } 
        ok = 0; 
        if(s * s == sum) dfs(0); 
        if(ok) printf("KHOOOOB!\n"); 
        else printf("HUTUTU!\n"); 
    } 
    return 0; 
} 

#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 40 + 10;
const int maxm = 10 + 10;
int s, n, num[maxm], side[maxn];
bool ok;

void dfs(int cur)
{
    if(ok) return;
    if(cur == n)
    {
        ok = 1;
        return;
    }

    int min_col = 1, i, j;     //找最凹處
    for(i = 2; i <= s; i++)
        if(side[i] < side[min_col])
            min_col = i;

    int border = s + 1;     //最凹處右界
    for(i = min_col + 1; i <= s; i++)
        if(side[i] != side[min_col])
        {
            border = i;
            break;
        }

    for(i = 10; i >= 1; i--)
    {
        if(num[i] > 0 && i <= s - side[min_col] && i <= border - min_col)
        {
            for(j = min_col; j < min_col + i; j++) side[j] += i;
            num[i]--;
            dfs(cur + 1);
            num[i]++;
            for(j = min_col; j < min_col + i; j++) side[j] -= i;
        }
    }
}

int main()
{
    int t, temp, sum, i;
    scanf("%d", &t);
    while(t--)
    {
        sum = 0;
        memset(num, 0, sizeof(num));
        memset(side, 0, sizeof(side));
        scanf("%d%d", &s, &n);
        for(i = 0; i < n; i++)
        {
            scanf("%d", &temp);
            num[temp]++;
            sum += temp * temp;
        }
        ok = 0;
        if(s * s == sum) dfs(0);
        if(ok) printf("KHOOOOB!\n");
        else printf("HUTUTU!\n");
    }
    return 0;
}