99久久精品这里只有精品,久久se精品一区二区,久久综合精品国产二区无码

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 流牛ζ木馬閱讀(1600) 評論(3) 編輯收藏引用

我用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

有編譯錯誤回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

# 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

# re: ACM PKU 1054 The Troublesome Frog　　學會剪枝[未登錄] 2009-08-04 22:04 123

ACM PKU 1054 The Troublesome Frog　　學會剪枝

評論

導航

統計

公告

常用鏈接

留言簿(6)

隨筆檔案

相冊

搜索

最新隨筆

最新評論

閱讀排行榜

評論排行榜

ACM PKU 1054 The Troublesome Frog 學會剪枝

評論

# 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

# re: ACM PKU 1054 The Troublesome Frog 學會剪枝[未登錄] 2009-08-04 22:04 123

導航

統計

公告

常用鏈接

留言簿(6)

隨筆檔案

相冊

搜索

最新隨筆

最新評論

閱讀排行榜

評論排行榜

ACM PKU 1054 The Troublesome Frog　　學會剪枝

# 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

# re: ACM PKU 1054 The Troublesome Frog　　學會剪枝[未登錄] 2009-08-04 22:04 123