一：题目大意
首先给定一个长宽为x,y的木板，现在需要把该木板分为N块。每次分割时，需要平行于所切割木板的长和宽，且需要切断。最后切割完成时需要所切割出的每个木板面积相等。现在需要求出最后y/x中和最小的一种方案。
二：题目分析
本题主要考查搜索技术和动态规划知识的运用。考虑到问题的特殊性，因为每次需要平行于长和宽，那么我们可以如此想，我们可以分割出N块木板需要进行N-1步。所以对于每一个木板，我们可以从两方面出发：
（1）把x边等分为n份，然后从1到n/2进行枚举。找到最小的一种方案。
（2）把y边等分为n份，然后从1到n/2进行枚举。找到最小的一种方案。
从这两种方案中选取最小的一种方案，并输出结果。
三： AC代码
#include<iostream> #include<cstdio> using namespace std; double x,y,N; double cal(double x,double y,int n) { if(x>y) { double t; t=x; x=y; y=t; }//让y成为最大边 if(n==1) return y/x; double ans=n*n*y/x;//这里就是指x分为n等分的情况时求得的值 for(int i=1;i<=n/2;i++) { double sump=cal(x*i/n,y,i)+cal(x*(n-i)/n,y,n-i);//将最小边x分为n份，然后递归枚举 if(sump<ans) ans=sump; } for(int i=1;i<n/2;i++) { double sump=cal(x,y*i/n,i)+cal(x,y*(n-i)/n,n-i);//将最大边y分为n份，然后递归枚举 if(sump<ans) ans=sump; } return ans; } int main() { int T; cin>>T; while(T--) { cin>>x>>y>>N; double ans=cal(x,y,N); printf("%.6lf ",ans);g } return 0; }
四：总结
（1）本题利用到剪枝技巧的使用
（2）学会根据已知限制条件枚举状态
（3）掌握递归求解技巧（递归结束条件）