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��ʾʣ�൰��Ĳ���,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);
}
}
}