#include <cstdio>
#include <string.h>
using namespace std;
int N,V,goodr,MinV[30],maxv[30][101][101];
int MaxV(int n,int r,int h){int s;s=0;
    if (maxv[n][r][h]>-1)return maxv[n][r][h];
    for (int i=0;i<n;i++)s+=(r-i)*(r-i)*(h-i);
    return maxv[n][r][h]=s;
}
int Min(int a,int b){return a>b?b:a;}
int f(int n,int v,int r,int h,int now){
    if (n==0){if (v==0)return now;return 100000000;}
    if (v<0 || now>goodr)return 100000000;
    int m;
    if (r==-1){
       for (int i=n;i*i<=v;i++)for (int j=(v-MinV[n-1])/i/i;j>=n;j--){
           m=f(n-1,v-i*i*j,i,j,i*i+2*i*j);
           if (m<goodr)goodr=m;
       }
       return goodr;
    }
    if (v<MinV[n])return 100000000;
    if (v>MaxV(n,r-1,h-1))return 100000000;
    if (r>1)if (now+2*v/(r-1)>goodr)return 100000000;//----------------------------------------------就是这句话!
    m=100000000;
    for (int i=r-1;i>=n;i--)for (int j=Min(((v-MinV[n-1])/i)/i,h-1);j>=n;j--){
        int w;
        w=f(n-1,v-i*i*j,i,j,2*i*j+now);
        if (w<m)m=w;
    }
    return m;
}     
int main()
{
    memset(maxv,0xff,sizeof(maxv));
    MinV[0]=0;
    for (int i=1;i<30;i++)MinV[i]=MinV[i-1]+i*i*i;
    goodr=100000000;
    scanf("%d %d",&V,&N);
    printf("%d\n",f(N,V,-1,-1,0));
    return 0;
}

• Re:一个剪枝把我靁翻了(532ms----->32ms) (1378) ningbohezhijun 2009-02-25 16:02:32
  • Re:一个剪枝把我靁翻了() (15) ningbohezhijun 2009-02-25 16:03:27