各位大哥，仁兄：帮忙看一下1190，怎么剪枝都超时............
#include <iostream>
using namespace std;
#define in(a,b) (a<b?a:b)
int n,m;
int minv[21],mins[21];
int best = 65535;

void solution(int v,int s,int floor,int r,int h)
{
    if(floor==0)
    {
        if(v==n && s<best)
            best=s;
        return ;
    }
    if(v+minv[floor-1]>n || s+mins[floor-1]>best || 2*(n-v)/r+s>best)
        return ;
    int i,j,hh;
    for(i=r-1;i>=floor;i--)
    {
        if(floor==m)
            s=i*i;
        hh=in((n-v)/(i*i),h-1);
        for(j=hh;j>=floor;j--)
            solution(v+i*i*j,s+2*i*j,floor-1,i,j);
    }

}

int main()
{
    int i;
    minv[0]=0;
    mins[0]=1;
    for(i=1;i<=20;i++)
    {
        minv[i]=minv[i-1]+i*i*i;
        mins[i]=mins[i-1]+2*i*i;
    }
    cin>>n;
    cin>>m;

    solution(0,0,m,n+1,n+1);
    if(best==65535)
    {
        cout<<0<<endl;
    }
    else
    {
        cout<<best<<endl;
    }
    return 0;
}
不知道该怎么剪了。。。。。。。。。。。。。。。

• Re:1190怎么剪枝。。。。。。。。。。。。。。 (1018) yuhailin 2009-05-22 17:11:45