http://blog.csdn.net/BeNoble_/article/details/53201146

强搜剪枝，没有什么技巧，把想到的不可能情况能剪就剪，然后时间就没有问题了。
```c++
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF = 2147483647;

int n,m,ans=INF;
int r[50],h[50];

void dfs(int hei,int last,int k)
{
if(hei==m+1&&last==0)
{
ans=min(k,ans);
}
else if(hei<=m)
{
if(k>=ans||last<=0) return;
if(hei==1)
{
for(h[1]=m;h[1]<n;h[1]++)
for(r[1]=m;r[1]<=(int)(sqrt(n/h[1]+0.5)+0.5);r[1]++) /* (int)(sqrt(n/h[1]+0.5)+0.5) */
dfs(2,n-r[1]*r[1]*h[1],r[1]*h[1]*2+r[1]*r[1]);
}
else
{
if(last >= (r[hei-1]*r[hei-1]*h[hei-1])*(m-hei+1)) return;
for(h[hei]=h[hei-1]-1;h[hei]>=(m-hei+1);h[hei]--)
for(r[hei]=(m-hei+1);r[hei]*r[hei]*h[hei]<=last&&r[hei]<r[hei-1];r[hei]++)
dfs(hei+1,last-r[hei]*r[hei]*h[hei],k+r[hei]*h[hei]*2);
}
}
}

int main()
{
scanf("%d%d",&n,&m);
memset(r,0,sizeof(r));
memset(h,0,sizeof(h));
r[0]=INF;h[0]=INF;

dfs(1,n,0);
printf("%d\n",ans==INF ? 0:ans);
return 0;
}
```

#include<cstdio>
long S=0x7fffff;
int n,m;
void dfs(int v,int r,int h,int l,int s)
{
if(s>S)//最优化剪枝，若小于最优解，则直接返回
return ;
if(l==1)
{
for(int r0=l;r0<=r;r0++)
if(v%(r0*r0)==0 && v/(r0*r0)<=h )
if(s+(v/r0)*2<S)
S=s+(v/r0)*2;
return ;
}
for(int h0=l;h0<=h;h0++)
for(int r0=l;r0<=r && r0*r0*h0<v;r0++)//可行化剪枝，易证得当还剩下L层时高度与半径最小为l，且要求体积必须小于剩下体积
if(l==m)
dfs(v-r0*r0*h0,r0-1,h0-1,l-1,s+r0*h0*2+r0*r0);
else dfs(v-r0*r0*h0,r0-1,h0-1,l-1,s+r0*h0*2);
return ;
}
int main()
{
scanf("%d %d",&n,&m);
dfs(n,n/m,n/m,m,0);
if(S==0x7fffff)
printf("0");
else printf("%ld",S);
return 0;
}

卡时间卡过去了
program p1297;
var n,m,sum,num,i,j:longint;
//
function make(p1:longint):longint;
var sum,i:longint;
begin
sum:=0;
for i:=1 to p1 do sum:=sum+i*i*i;
exit(sum);
end;
//
function min(p1,p2:longint):longint;
begin
if p1>p2 then exit(p2)
else exit(p1);
end;
//
procedure dfs(k,s,h,v:longint);
var i,j:longint;
begin
if v<make(m-k+1) then exit;
if k=m+1 then
begin
if v<>0 then exit;
num:=num+s*h*2;
if num<sum then sum:=num;
num:=num-s*h*2;
exit;
end;
num:=num+s*h*2;
if num>sum then
begin
num:=num-s*h*2;
exit;
end;
for i:=m-k+1 to s-1 do
for j:=m-k+1 to min(h-1,v div (i*i)) do
dfs(k+1,i,j,v-i*i*j);
num:=num-s*h*2;
end;
//
begin
read(n);
read(m);sum:=1000000;
for i:=m to n do
for j:=m to n div (i*i) do
begin
num:=i*i;
dfs(2,i,j,n-i*j*i);
end;
if sum=1000000 then sum:=0;
write(sum);
end.

无解的太坑了....一直没想起会无解....额，我不会告诉你测试数据无解那个是1000 7的...开玩笑，我怎么可能告诉你输出是0呢...

#include <iostream>

using namespace std;

int N, M;
int minS = 9999999;

void DFS(int n, int v, int s, int r, int h)
{
int i, j;

if (n == 0) {
if (s < minS && v == N) minS = s;
}

// 最优性剪枝
if (s > minS) return;
// 可行性剪枝
if (v > N) return;
// 最优性剪枝，判断当前状态下能构成的最小面积是否大于minS（强力剪枝：if s+2*(n-v)/r>=mins then exit;）
if ((s + 2 * (N - v) / r) >= minS) return;
// 可行性剪枝
if ((r - 1) < n || (h - 1) < n) return;

int nv, ns;
for (i = r - 1; i > 0; --i) {
for (j = h - 1; j > 0; --j) {
nv = v + i * i * j;
ns = s + 2 * i * j;
if (n == M) ns += i * i;
DFS(n - 1, nv, ns, i, j);
}
}
}

int main()
{
cin >> N >> M;
DFS(M, 0, 0, 100, 100);
if (minS == 9999999) minS = 0;
cout << minS;
return 0;
}

program cake;
var
i,r,h,vn,rn,hn,sn,best,m,n:integer;
mins,minv:array[0..100] of integer;
{=======prunning=======}
procedure prunning;
var
k:integer;
begin
for k:=1 to n-1 do
begin
minv[k]:=minv[k-1]+k*k*k;
mins[k]:=mins[k-1]+2*k*k;
end;
end;
{=========dfs========}
procedure dfs(i,rn,hn,vn,sn:integer);
var
r,h:integer;
begin
if i>n then
begin
if (sn<best) and (vn=0) then
best:=sn;
exit;
end;
if (sn+(2*vn) div rn < best) and (sn+mins[n-i+1] < best) and (vn >= minv[n-i+1]) and (vn>=0) then
begin
for r:=rn-1 downto n-i+1 do
for h:=hn-1 downto n-i+1 do
dfs(i+1,r,h,vn-r*r*h,sn+2*r*h);
end;
end;
{================main===============}
begin
best:=maxint;
fillchar(mins,sizeof(mins),0);
fillchar(minv,sizeof(minv),0);
readln(m);
readln(n);
prunning;
for r:=trunc(sqrt((m-minv[n-1]) div n)) downto n do
for h:=(m-minv[n-1]) div (r*r) downto n do
begin
dfs(2,r,h,m-r*r*h,2*r*h+r*r);
end;
if best<maxint then
writeln(best)
else
writeln(0);
end.

program cake;
var
n,m,sum:longint;
i,j:longint;
procedure go(o,r,h,v,s:longint);
var
k,l:longint;
begin
if o=0
then
begin
if (v=0)and(s<sum)
then
sum:=s;
exit;
end;
k:=0;
for l:=1 to o do
k:=k+l*l*l;
if v<k //可行性剪枝，判断剩下的体积是否足够做蛋糕
then
exit;
k:=0;
for l:=1 to o do
k:=k+(r-l)*(r-l)*(r-l); //可行性剪枝，判断剩下的体积是否做得完
if v>k
then
exit;
if s>sum //最优化剪枝，判断面积是否符合条件
then
exit;
if s+2*v/r>sum //最优化剪枝，剩下的s>=2*h*r=2*v/r
then
exit;
for k:=r-1 downto o do
for l:=h-1 downto o do
go(o-1,k,l,v-k*k*l,s+2*k*l)
end;

begin
readln(n);
readln(m);
sum:=maxlongint;
for i:=m to trunc(sqrt(n)) do
for j:=m to trunc(n/i/i) do
go(m-1,i,j,n-i*i*j,i*i+2*i*j);
if sum=maxlongint
then
sum:=0;
writeln(sum);
end.
为什么最后一个点错了？求大牛指导

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

一点特殊剪枝没有,秒杀.........

program noi;

var

n,m,r,h,i:longint;

ans:longint;

minv:array[0..20]of longint;

function min(a,b:longint):longint;

begin

if ab then max:=a else max:=b;

end;

function maxv(r,h,k:longint):longint;

var i:longint;

begin

maxv:=0;

for i:=1 to k do

begin

dec(r);dec(h);

if (r=v)and(minv[k-1]

Accepted 有效得分：100 有效耗时：0ms

伟大的数学推理剪枝~~~

program xiti;

type longint=integer;

var i,j,n,m,ans:longint;

t:array[1..20]of longint;

procedure find(cs,r,h,s,v:longint);

var ii,jj,qqq,ppp:longint;

begin

if s>=ans then exit;

if (cs=m)and(v=0) then

ans:=s;

if (cs=m)or(v=0) then

exit;

if v

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

以前~

一直没什么思路

写了个裸搜

没过

今天

灵感突发~

加两个剪枝~

居然过了~

囧~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案错误...程序输出比正确答案长

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 88ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：232ms

囧~~~~~

原来是0........囧~~~~~

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-var s,v,h,i,j,k,l,o,p,m,n,q,w,smin:longint;

s1,v1,r1,h1:longint;

minv:longint;

procedure sea(i,ri,hi,si,vi:longint);

var j,k,l,Rijia1,Hijia1,Sijia1,Vijia1:longint;

begin

minv:=0;

if (i=m) then if (smin>si) and( vi=0) then begin smin:=si;exit;end;

for k:=1 to m-i-1 do

minv:=minv+sqr(k)*k;

if si+2*vi/ri>smin then exit;

if vi

├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms-------------------------program cgb; var n,m,r,h,i:longint; opt:longint; minv:array[0..20]of longint; function min(a,b:longint):longint; begin if ab then max:=a else max:=b; end; function maxv(r,h,k:longint):longint; var i:longint; begin maxv:=0; for i:=1 to k do begin dec(r);dec(h); if (r=v)and(minv[k-1]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 244ms

├ 测试数据 08：答案正确... 25ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：269ms

剪枝太多了反而使程序更复杂,不能秒杀了......

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

只有两个常规的剪纸

if(ss*(N-d+1)+s>re) break;

if(vv*(N-d+1)+v>V) break;

数据弱~连我这么弱的人也全0ms

加一个最优化剪枝就AC了，秒杀！

判断 2*r*(n-v)/r/r+s>=best 就可以了！

搜索剪枝

VJ上NOI中最好做的一题

交了好多遍,数据蛮强的(可能我太弱了)

1.最优解剪枝

2.可行解剪枝(上限，下限)

3.细节

最优解别弄太大3000最够了