论坛 › 【编程】编程圣殿 › 1666应该如何优化,我狂超时!

晓东 发表于 2005-8-8 22:09

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

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

晓东 发表于 2005-8-8 22:10

#include<stdio.h>
int flag;
void search(int num,int from)
{
        int i;
        if(num>=300)return;
        flag++;
        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);
        }
}

sheep426 发表于 2005-8-14 18:27

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

sasadong 发表于 2005-10-27 02:17

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


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

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

查看完整版本: 1666应该如何优化,我狂超时!