1666应该如何优化,我狂超时!

晓东

http://acm.zju.edu.cn/show_problem.php?pid=1666
这个题我用递归,不过不知道如何优化,所以猜超时,哪位有空的研究一下,然后告知.

晓东

#include<stdio.h>
int flag[301];
void search(int num,int from)
{
        int i;
        if(num>=300)return;
        flag[num]++;
        for(i=from;i<18;i++)
                search(num+i*i,i);
        return;
}
main()
{
        int i,n;
        for(i=1;i<300;i++)
                flag=0;
        for(i=1;i<18;i++)
        {
                search(i*i,i);
        }
        while(1)
        {
                scanf("%d",&n);
                printf("%d\n",flag[n]);
        }
}

sheep426

好像很容易抵推，记录中间的值
动态规划用于非最优化问题

sasadong

Originally posted by 晓东 at 2005-8-8 22:10:
#include<stdio.h>
int flag[301];
void search(int num,int from)
{
        int i;
        if(num>=300)return;
        flag[num]++;
        for(i=from;i<18;i++)
                search(num+i*i,i);
        return;
}
main()
{
         ...

for(i=1;i<300;i++)
                flag=0;

这个我一般用memset的，全部设置为0，简单。嘿嘿