首页 > 代码库 > 【poj1020】 Anniversary Cake
【poj1020】 Anniversary Cake
http://poj.org/problem?id=1020 (题目链接)
题意
有一个S*S的大蛋糕，还有许多正方形的小蛋糕，问能否将大蛋糕完整的分成所有的小蛋糕，不能有剩余。
Solution
像这种看起来很麻烦的基本上都是水题，然而poj上的所谓水题，我也是呵呵了。
在根据题意做完若干判断剪枝后，我们开始搜索。因为蛋糕不能有剩余，所以搜索就很好搜了，刚开始没注意，不知道不允许剩余，直接参考了别人的程序= =。详情请见：题解
代码
// poj1020#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define MOD 100000000#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=100;int a[maxn],c[maxn],n,S;;bool dfs(int x) { if (x==n) return 1; int tmp=50,p; for (int i=1;i<=S;i++) if (tmp>c[i]) tmp=c[i],p=i; for (int i=10;i;i--) //枚举 if (a[i] && S-c[p]>=i && S-p+1>=i) { int w=0; for (int j=p;j<=p+i-1;j++) { if (c[j]==c[p]) w++; //因为必须放满，所以不能留空 else break; } if (w==i) { a[i]--; for (int j=p;j<=p+i-1;j++) c[j]+=i; if (dfs(x+1)) return 1; a[i]++; for (int j=p;j<=p+i-1;j++) c[j]-=i; } } return 0;}int main() { int T;scanf("%d",&T); while (T--) { memset(a,0,sizeof(a)); memset(c,0,sizeof(c)); scanf("%d%d",&S,&n); int cnt=0,area=0; for (int x,i=1;i<=n;i++) { scanf("%d",&x); area+=x*x; a[x]++; if (x>S/2) cnt++; } if (cnt>1 || area!=S*S) {printf("HUTUTU!\n");continue;} if (dfs(0)) printf("KHOOOOB!\n"); else printf("HUTUTU!\n"); } return 0;}
【poj1020】 Anniversary Cake
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。