Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 真不错……

Posted by 1200017623 at 2013-02-27 13:19:03 on Problem 1020
```#ifdef TIME_CHECK
#include<ctime>
#endif

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

int nCase,nTotalSize,nCakeNum; //The global variable is needed in dfs() function
const int MAX = 41;  //The maximum size of the cake is sqrt(16 * 10 * 10) = 40
bool isUsed[MAX][MAX] = {false};      //mark whether the cake has been given away

struct CakePiece{
int m_nSize;
bool m_bUsed;
}nCakePiece[17] = {0};      //The size of each cake

inline bool myCmp(CakePiece a,CakePiece b){
return a.m_nSize > b.m_nSize;
}
//Find the first grid not occupied
void FindPosition(int& x ,int& y){
for(int i = 0;i < nTotalSize;++i){
for(int j = 0;j < nTotalSize;++j){
if(isUsed[i][j] == false){
x = i,y = j;
return;
}
}
}
}

bool isOkay(int num,int x,int y){
//The remaining place is not wide enough
int size = nCakePiece[num].m_nSize;
if(x + size > nTotalSize || y + size > nTotalSize)return false;
for(int i = 0;i < size;++i){
if(isUsed[x + i][y] == true
|| isUsed[x][y + i] == true)return false;
}return true;
}
//Try to cut a piece, mark all the relevant grids true
void CutPiece(int num,int x,int y){
int nSize = nCakePiece[num].m_nSize;
nCakePiece[num].m_bUsed = true;
for(int i = x;i < x + nSize;++i){
for(int j = y;j < y + nSize;++j){
isUsed[i][j] = true;
}
}
}
//Recover a piece, mark all the relevant grids false
void Recover(int num,int x,int y){
int nSize = nCakePiece[num].m_nSize;
nCakePiece[num].m_bUsed = false;
for(int i = x;i < x + nSize;++i){
for(int j = y;j < y + nSize;++j){
isUsed[i][j] = false;
}
}
}

//Srart stuffing, always from top-left
bool dfs(int n){      //Try and stuff the nth cake piece
if(n == nCakeNum)return true;
int cur_x = 0,cur_y = 0;   //determine where to put the cake
FindPosition(cur_x,cur_y);
for(int i = 0;i < nCakeNum;++i){
if(nCakePiece[i].m_bUsed == false && isOkay(i,cur_x,cur_y)){
//pruning: avoid try the same size piece
if(i != 0 && nCakePiece[i-1].m_bUsed == false
&& nCakePiece[i].m_nSize == nCakePiece[i-1].m_nSize)
continue;

CutPiece(i,cur_x,cur_y);

if(dfs(n+1) == true)return true;
else Recover(i,cur_x,cur_y);
}
}
return false;
}

int main(){
clock_t s,e;
scanf("%d",&nCase);
s = clock();
for(;nCase;--nCase){
scanf("%d%d",&nTotalSize,&nCakeNum);

int nAreaSum = 0;
for(int i = 0;i < nCakeNum;++i){
scanf("%d",&nCakePiece[i].m_nSize);
nCakePiece[i].m_bUsed = false;
nAreaSum += nCakePiece[i].m_nSize * nCakePiece[i].m_nSize;
}
if(nAreaSum != nTotalSize * nTotalSize){
printf("HUTUTU!\n");continue;
}
//Sort the cake in size order
sort(nCakePiece,nCakePiece + nCakeNum,myCmp);
//Start search, always begin from the top left;
memset(isUsed,false,MAX * MAX * sizeof(bool));
if(dfs(0) == true)printf("KHOOOOB!\n");
else printf("HUTUTU!\n");
}
e = clock();
printf("%d ms\n",e-s);
system("PAUSE");
return 0;
}```

Followed by: