Poj Solution 1190

http://poj.org/problem?id=1190

/* @author: */
import java.util.Scanner;
public class Main {
static int end,min;   
static int M,S;
static int dfs(int v,int m,int lastr,int lasth)   
{   
    if(m==0)   
    {   
        //������Ϊ0ʱ��ʣ�����Ϊ0,˵��˴�����ɹ�,Ӧ����   
        if(v>0||v< 0)   
            return 0;   
        else  
        {   
            //Ϊ0,����Ŀ���н�,�жϵ�ǰ�������Ƿ���Ѿ��õ�����С���С,��С���û�.   
            end=1;   
            if(min< S)   
                S=min;   
            return 0;   
        }   
    }   
    int i,t=0,j,k,temp;   
    //����m���������   
    for(i=1;i<=m;i++)   
        t+=i*i*i;   
    //��ǰ������С���С,����   
    if(v< t)   
        return 0;   
    t-=m*m*m;   
    int maxr,maxh;   
    //���㵱ǰ��ײ����ܹ��ﵽ�����뾶.   
    maxr=(int)Math.sqrt((v-t)*1.0/m)< lastr?(int)Math.sqrt((v-t)*1.0/m):lastr;   
    for(i=maxr;i>=m;i--)   
    {   
        //����ȷ���뾶��������ܹ��ﵽ�����߶�   
        maxh=(v-t)/(i*i)< lasth?(v-t)/(i*i):lasth;   
        //����   
        for(j=maxh;j>=m;j--)   
        {   
            temp=0;   
            //��ݵ�ǰ��ײ�ȷ��m�㵰���ܴﵽ��������.   
            for(k=0;k<=m-1;k++)   
                temp+=(i-k)*(i-k)*(j-k);   
            //���������,�϶�����ʣ��,����   
            if(v>temp)   
                break;   
            int tempv=v-i*i*j;   
            //��һ��ʱҪ�����ϱ�������   
            if(m==M)   
            {   
                if(i*i< S)   
                min=i*i;   
                else  
                {   
                    tempv=v;   
                    continue;   
                }   
            }   
            //���ϲ����,��ÿһ�㶼����   
            min+=2*i*j;   
            //��ǰ�õ�������Ѿ�������֪����С������,����ľͲ�����������,ֱ�ӷ���   
            if(min>S)   
            {   
                tempv=v;   
                min-=2*i*j;   
                continue;   
            }   
            dfs(tempv,m-1,i-1,j-1);   
            //���ݺ�Ҫ�ָ����   
            min-=2*i*j;   
        }   
    }   
    return 0;   
}   

public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
 ///��������,�����Լ����֦�Ż�   
//S��ʾ��С���   
int N;   
//end��ʼΪ0,�н����Ϊ1.min��4��ʾÿ�γɹ�����ʱ�����������   
//v��ʾ��ǰʣ������,m��ʾʣ�൰��IJ���,lastr��ʾ�Ѿ�ȷ������һ�㵰��İ뾶,lasthͬ��   
    
    while(sc.hasNext())   
    {  
       N=sc.nextInt();
       M=sc.nextInt();
 
        int t=0;   
        end=0;   
        S=100000;   
        dfs(N,M,1000,1000);   
        if(end==0)   
            S=0;   
        System.out.printf("%dn",S);   
    }   
   }
}  

											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *