青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 
*= (PLANT *)a, *= (PLANT *)b;
       
if(x->== y->x)    return x->- y->y;
       
return 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 流牛ζ木馬 閱讀(1614) 評論(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

有編譯錯誤  回復  更多評論   

<2007年11月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

導航

統計

公告

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

常用鏈接

留言簿(6)

隨筆檔案

相冊

搜索

最新隨筆

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国产日韩亚洲欧美精品| 久久疯狂做爰流白浆xx| 香蕉成人伊视频在线观看 | 欧美一区二区三区四区在线观看 | 久久se精品一区精品二区| 性做久久久久久免费观看欧美| 亚洲一区欧美| 久久久www成人免费毛片麻豆| 麻豆av福利av久久av| 欧美日本中文字幕| 国产日本欧美视频| 亚洲国产精品久久久久婷婷老年| 亚洲理伦电影| 亚洲欧美国产精品桃花| 久久久久久久综合| 亚洲激情自拍| 亚洲午夜日本在线观看| 久久精品人人爽| 欧美福利一区二区三区| 国产精品久久久久久久久久久久久久 | 欧美成人午夜激情在线| 欧美午夜精品久久久久久孕妇| 国产精品毛片在线| 在线精品国产欧美| 亚洲欧美福利一区二区| 欧美激情1区2区3区| 亚洲一区二区三区中文字幕| 久久久噜噜噜久久久| 欧美日韩综合视频网址| 黄色亚洲网站| 亚洲尤物在线视频观看| 久久久99免费视频| 欧美一区二区三区日韩| 欧美国产大片| 国产亚洲激情在线| 一区二区欧美视频| 欧美国产一区二区| 久久不射2019中文字幕| 国产乱码精品| 亚洲欧美视频在线观看| 日韩午夜精品| 欧美日韩高清在线播放| 亚洲人成网在线播放| 久久中文字幕一区| 欧美一区午夜精品| 国产欧美日韩精品在线| 午夜性色一区二区三区免费视频| 日韩天堂av| 欧美视频导航| 亚洲一区二区三区四区五区黄| 亚洲黄色成人| 欧美精品久久一区| 亚洲精品免费在线| 亚洲国产日韩精品| 欧美高清视频在线播放| 亚洲国产美女久久久久| 欧美福利在线| 乱人伦精品视频在线观看| 在线观看精品| 欧美激情五月| 欧美国产综合视频| 亚洲精选一区| 亚洲精品乱码久久久久久久久| 欧美成在线观看| av成人激情| 一区二区91| 国产欧美日韩在线| 久久一综合视频| 美女精品一区| 一本色道精品久久一区二区三区| 亚洲日韩视频| 国产精品视频免费| 久久夜色精品国产亚洲aⅴ| 久久久91精品| 亚洲精品久久久久| 亚洲一区视频| 在线看视频不卡| 亚洲精品影视| 国产亚洲va综合人人澡精品| 久久久久一区二区| 蜜桃久久av一区| 亚洲午夜久久久久久尤物 | 久久乐国产精品| 最新日韩精品| 在线亚洲观看| 国内精品久久久| 亚洲黄一区二区三区| 国产精品久久久久9999吃药| 久久免费偷拍视频| 欧美精品福利视频| 久久国产婷婷国产香蕉| 亚洲一区在线免费| 亚洲国产另类精品专区 | 欧美日韩午夜| 亚洲欧美日韩国产综合精品二区| 亚洲精品一区二区三区不| 欧美国产一区二区三区激情无套| 在线精品福利| 亚洲欧洲视频| 国产精品久久9| 久久精品免费| 久久一区欧美| 99国产精品久久久久久久久久| 亚洲理论在线观看| 国产精品久久网| 久久激情五月婷婷| 久久久精品性| 亚洲精选91| 99精品国产在热久久下载| 欧美性生交xxxxx久久久| 亚洲欧美网站| 久久久精品性| 一本在线高清不卡dvd| 亚洲午夜精品一区二区三区他趣| 国产日韩在线看| 亚洲激情小视频| 国产精品夜色7777狼人| 久久综合图片| 国产麻豆午夜三级精品| av成人免费观看| 一区电影在线观看| 欧美激情网友自拍| 欧美激情精品久久久久久黑人| 狠狠色丁香婷综合久久| 亚洲私拍自拍| 亚洲人成人77777线观看| 国产精品人人做人人爽 | 亚洲第一精品电影| 伊人成综合网伊人222| 欧美怡红院视频| 欧美一区二粉嫩精品国产一线天| 欧美日韩情趣电影| 亚洲免费观看视频| 在线综合欧美| 国产精品对白刺激久久久| aa级大片欧美| 午夜精品久久久久久久99水蜜桃 | 美国十次了思思久久精品导航| 国产午夜精品一区二区三区欧美| 亚洲性夜色噜噜噜7777| 午夜在线精品偷拍| 国产日韩欧美综合一区| 欧美在线一二三四区| 久久一区二区三区四区| 亚洲国产精品久久久| 欧美激情一区二区三区| 99国产精品久久久久久久| 久久免费视频在线| 欧美/亚洲一区| 欧美黄色免费| 中文国产成人精品久久一| 亚洲永久免费视频| 99精品国产99久久久久久福利| 久久免费精品视频| 在线观看亚洲精品视频| 午夜精品久久久久久久久久久| 艳女tv在线观看国产一区| 六月婷婷一区| 日韩一级精品| 亚洲欧美中文另类| 国产一区二区高清视频| 久久久精品免费视频| 欧美成人一品| 亚洲高清久久久| 欧美激情精品久久久久久大尺度 | 欧美视频在线观看一区二区| 亚洲最新视频在线播放| 欧美专区日韩专区| 1024成人| 国产精品久久久久久久免费软件| 亚洲欧美日韩一区在线观看| 美女黄网久久| 亚洲午夜日本在线观看| 国内精品久久久久久久影视麻豆 | 女人天堂亚洲aⅴ在线观看| 亚洲免费福利视频| 国产人久久人人人人爽| 蜜臀99久久精品久久久久久软件| 日韩一区二区精品在线观看| 久久黄色影院| 宅男在线国产精品| 亚洲高清网站| 国产视频欧美视频| 欧美精品1区2区3区| 久久aⅴ乱码一区二区三区| 亚洲美女在线国产| 欧美成年人视频网站| 午夜一区二区三区不卡视频| 亚洲人成在线免费观看| 国产目拍亚洲精品99久久精品| 欧美成人免费在线观看| 午夜精品99久久免费| 99爱精品视频| 91久久精品国产91久久| 亚洲一区日本| 亚洲视频免费在线| 亚洲二区在线视频| 国产中文一区| 国产欧美一区二区三区国产幕精品 | 91久久精品国产91性色|