洛谷P1731 生日蛋糕 洛谷P1731 生日蛋糕 题目传送门 题解 搜索+剪枝: 众所周知,暴力搜索的时间复杂度是O(N!)的,也就是说,仅仅能过N<10左右的数据。而我们优化搜索的方式一般有两种,一种是优化枚举顺序,使得答案更早的出现。另一种是剪枝,去除不可能的情况。 对于本题而言,我们有三种剪枝策略: 1.如果剩余体积小于向上能叠出的最小体积,则停 2.如果剩余体积大于向上能叠出的最大体积,则停 3.如果当前答案加上向上所能获取的最小答案仍大于ans,则停 #include<cstdio>#include<algorithm>//#pragma GCC optimize(2)using namespace std;#define maxx 10010int n,m;#define inf 1000000001int ans = inf;int vmin[maxx<<1];int smin[maxx<<1];int vmax[maxx<<1][50];void dfs(int r,int h,int s,int v,int dep){ if(dep>m) { if(v==0) ans = min(ans,s); return; } if(v<vmin[m-dep]) return; if(s+smin[m-dep]>=ans) return; int vmax = 0; for(int i=m-dep+1;i>=1;i--) vmax+=(r-i)*(r-i)*(h-i); if(v>vmax) return; for(int i=r-1;i>=m-dep+1;i--) { for(int j=h-1;j>=m-dep+1;j--) dfs(i,j,s+2*i*j,v-i*i*j,dep+1); }}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { vmin[i]=vmin[i-1]+i*i*i; smin[i]=smin[i-1]+i*i