据说暴力地枚举每种切法也能过，但更合理的算法应该是动态规划。

考虑下面两点
（1）原始矩形切i(1<=i<=p)刀的最优解一定是从切了(i-1)刀的最优解上再加一刀得到的。
（2）原始矩形切了i刀后，无论这前i刀是以何种顺序，留下的图形显然都是固定的。
于是，总状态数从原来的p!（暴力法）减少到了pow(2,p)个。
以上两点想通了，具体算法很简单，不再赘述了。