ACM PKU 1543 Perfect Cubes 简单题,简单剪枝

http://acm.pku.edu.cn/JudgeOnline/problem?id=1543

完完全全的O(n4)算法
注意几个剪枝条件

Source Code

Problem: 1543  User: lnmm 
Memory: 64K  Time: 15MS 
Language: C++  Result: Accepted 

Source Code 
#include"stdio.h"

void main()
{
    long int cube[101];
    int n,i,a,b,c,d;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        cube[i]=i*i*i;
    for(a=6;a<=n;a++)
        for(b=2;b<n;b++)
        {
            if(cube[a]<cube[b]+cube[b+1]+cube[b+2])break;
            for(c=b+1;c<a;c++)
            {
                if(cube[a]<cube[b]+cube[c]+cube[c+1])break;
                for(d=c+1;d<a;d++)
                if(cube[a]==cube[b]+cube[c]+cube[d])
                    printf("Cube = %d, Triple = (%d,%d,%d)\n",a,b,c,d);

            }
        }

}

posted on 2007-11-13 20:34 流牛ζ木马 阅读(1150) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2007年9月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

导航

统计

公告

MY Email/MSN :mars1021@163.com QQ : 27402040 流牛ζ木马

常用链接

留言簿(6)

随笔档案

相册

搜索

最新随笔

最新评论

阅读排行榜

评论排行榜