本文主要是介绍POJ - 1020 Anniversary Cake，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有一块边长为BoxSize的正方形的大蛋糕，现在给出n块不同尺寸的正方形的小蛋糕的边长，问是否能把大蛋糕按恰好切割为这n块小蛋糕，要求每块小蛋糕必须为整块。
思路：有技巧性的DFS，这里有一篇写的很好的：点击打开链接
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;int BoxSize,n;
int SizeNum[11];
int col[41];bool dfs(int FillNum){if (FillNum == n)return true;int min = 50;int prow;for (int i = 1; i <= BoxSize; i++)if (min > col[i]){min = col[i];prow = i;}for (int size = 10; size >= 1; size--){if (!SizeNum[size])continue;int wide = 0;if (BoxSize-col[prow] >= size && BoxSize-prow+1 >= size){int wide = 0;for (int r = prow; r <= prow+size-1; r++){if (col[r] <= col[prow]){wide++;continue;}break;}if (wide >= size){int r;SizeNum[size]--;for (r = prow; r <= prow+size-1; r++)col[r] += size;if (dfs(FillNum+1))return true;SizeNum[size]++;for (r = prow; r <= prow+size-1; r++)col[r] -= size;}}}return false;
}int main(){int cas;scanf("%d",&cas);for (int t = 1; t <= cas; t++){memset(SizeNum,0,sizeof(SizeNum));memset(col,0,sizeof(col));scanf("%d%d",&BoxSize,&n);int cnt=0,area=0;for (int i = 1; i <= n; i++){int size;scanf("%d",&size);area += size*size;SizeNum[size]++;if (size > BoxSize/2)cnt++;}if (cnt > 1 || area != BoxSize*BoxSize){printf("HUTUTU!\n");continue;}if (dfs(0))printf("KHOOOOB!\n");else printf("HUTUTU!\n");}return 0;
}这篇关于POJ - 1020 Anniversary Cake的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
