> #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:一个剪枝把我靁翻了() (15) ningbohezhijun 2009-02-25 16:03:27