ACM PKU 1054 The Troublesome Frog　　学会剪枝

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

有的说是入门级剪枝，有的说是剪枝条件很强，，呵呵，无论怎样，今天我终于成功剪枝了．　以前也是做了很久的．
注意qsort和bsearch 的使用
#include "stdio.h"

#include "stdlib.h"
 
struct PLANT
{
       int x, y;
}plant[5001];
 
int row, col, n;
 
int cmp(const void *a, const void *b)
{
       PLANT *x = (PLANT *)a, *y = (PLANT *)b;
       if(x->x == y->x)    return x->y - y->y;
       return x->x - y->x;
}
 
void input()
{
       int i;
       scanf("%d %d", &row, &col);
       scanf("%d", &n);
       for(i=0; i<n; i++)
              scanf("%d %d", &plant[i].x, &plant[i].y);
}
 
int solve();
 
int main()
{
       input();
       qsort(plant, n, sizeof(PLANT), cmp);
       int temp = solve();
       if(temp > 2)                                //题目要求 答案一定大于等于3
              printf("%d\n", temp);
       else
              printf("0\n");
       return 0;
}
 
int solve()
{
    int max = 0, temp;
    int i, j;
    PLANT n1, n2, jump, next;
    
    for(i=0; i<n; i++)
    {
        for(j=i+1; j<n; j++)
        {
            temp = 2;
            n1 = plant[i];
            n2 = plant[j];
            jump.x = plant[j].x - plant[i].x;
            jump.y = plant[j].y - plant[i].y;
            if(n1.x - jump.x > 0 && (n1.y - jump.y >0 && n1.y - jump.y <=col) )
            //只能从外面逃入
                continue;
            if(n1.x + max*jump.x > row || n1.y + max*jump.y > col || n1.y + max*jump.y <= 0)
            //超出范围
                continue;
            next.x = plant[j].x + jump.x;
            next.y = plant[j].y + jump.y;
            while(next.x <= row && next.y <= col && next.x > 0 && next.y > 0)
            {
                PLANT * a = (PLANT *) bsearch( &next, plant, n, sizeof(PLANT), cmp);
               
                //bsearch 二分法
                if(a == NULL)
                {
                    temp = 0;
                    break;
                }
                temp ++;           
                next.x += jump.x;
                next.y += jump.y;
            }
            if(temp > max)    max = temp;
        }
    }    
    return max;
}

posted on 2007-11-13 22:24 流牛ζ木马 阅读(1571) 评论(3)  编辑 收藏 引用

评论

# re: ACM PKU 1054 The Troublesome Frog　　学会剪枝 2007-11-18 13:39 Run&Run

你"跳"字打错了......  回复  更多评论   

# re: ACM PKU 1054 The Troublesome Frog　　学会剪枝 2008-01-13 14:51 Pope

我用std::sort,把<x, y>封装成class，结果超时，然后改成qsort，用数组表示就AC了。看来C++在数值计算方面的优势不是很大。
要是没有你的代码，没看到
if(n1.x + max*jump.x > row || n1.y + max*jump.y > col || n1.y + max*jump.y <= 0)
//超出范围
continue;
这一句剪枝，我也没这么快AC。
谢谢！  回复  更多评论   

# re: ACM PKU 1054 The Troublesome Frog　　学会剪枝[未登录] 2009-08-04 22:04 123

有编译错误  回复  更多评论   


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


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

导航

统计

公告

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

常用链接

留言簿(6)

随笔档案

相册

搜索

最新随笔

最新评论

阅读排行榜

评论排行榜