• <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>
            

    
            

            




            







												


        



			
			


			
            
				
					
	
            
		
            
			ACM PKU 1054 The Troublesome Frog　　學(xué)會(huì)剪枝
		
            
		http://acm.pku.edu.cn/JudgeOnline/problem?id=1054

            有的說是入門級(jí)剪枝，有的說是剪枝條件很強(qiáng)，，呵呵，無論怎樣，今天我終于成功剪枝了．　以前也是做了很久的．
            注意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 流牛ζ木馬 閱讀(1595) 評(píng)論(3)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    


            

            評(píng)論
            
	
	
			
            
				# re: ACM PKU 1054 The Troublesome Frog　　學(xué)會(huì)剪枝
					
						2007-11-18 13:39
					
				Run&Run
			
            
			
            
				你"跳"字打錯(cuò)了......  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: ACM PKU 1054 The Troublesome Frog　　學(xué)會(huì)剪枝
					
						2008-01-13 14:51
					
				Pope
			
            
			
            
				我用std::sort,把<x, y>封裝成class，結(jié)果超時(shí)，然后改成qsort，用數(shù)組表示就AC了。看來C++在數(shù)值計(jì)算方面的優(yōu)勢(shì)不是很大。

            要是沒有你的代碼，沒看到

            if(n1.x + max*jump.x > row || n1.y + max*jump.y > col || n1.y + max*jump.y <= 0)

                        //超出范圍

                            continue;

            這一句剪枝，我也沒這么快AC。

            謝謝！  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: ACM PKU 1054 The Troublesome Frog　　學(xué)會(huì)剪枝[未登錄]
					
						2009-08-04 22:04
					
				123
			
            
			
            
				有編譯錯(cuò)誤  回復(fù)  更多評(píng)論
				  
			
            
		

            




            



            


            

	
            
		
		
            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            
		
            
		
				
		
		
		
            
		
            			
		
		
		
		
            
		
            
			
		
            
		
            
			
		
            
		
            
			
            網(wǎng)站導(dǎo)航:
			博客園  
			IT新聞  
			BlogJava  			
			博問  
			Chat2DB  
			管理
			
            		
		
            
		
            
			
				

            


            

            		
		
            
	
            	

            



            

				
				

			
            
			
            
				
					
            
	
            
		
            <2007年11月>
            
	
            日一二三四五六
            28293031123
            45678910
            11121314151617
            18192021222324
            2526272829301
            2345678
            

            

					

            導(dǎo)航
            

					

            統(tǒng)計(jì)
            
	
					

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



            






            

            



					

            常用鏈接
            


            留言簿(6)
            


		
            隨筆檔案
            
		
				
			
	
		
            相冊(cè)
            
		
				
			
	



            搜索
            



            最新隨筆
            

            


            


            最新評(píng)論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評(píng)論排行榜
            


				
			
            
			
			
			
			
			 

	

            






            

            


            



                
    







            
	   
	



久久久久久久精品妇女99|
999久久久免费精品国产|
久久亚洲精品无码VA大香大香|
中文字幕无码av激情不卡久久|
欧美一区二区久久精品|
国产精品美女久久久|
久久天天躁狠狠躁夜夜不卡|
欧洲精品久久久av无码电影|
精品久久久久久国产三级|
日韩乱码人妻无码中文字幕久久
|
MM131亚洲国产美女久久|
国产精品免费久久久久电影网|
18岁日韩内射颜射午夜久久成人|
66精品综合久久久久久久|
无码AV中文字幕久久专区|
久久亚洲国产成人影院网站|
精品熟女少妇av免费久久|
欧美午夜A∨大片久久|
亚洲国产精久久久久久久|
人妻久久久一区二区三区|
久久影院久久香蕉国产线看观看|
精品九九久久国内精品|
久久九九久精品国产免费直播|
久久国产视频99电影|
国产成人久久久精品二区三区
|
99久久国产热无码精品免费久久久久|
久久青青色综合|
亚洲国产精品无码久久九九|
99久久99久久精品国产|
久久中文字幕一区二区|
久久不见久久见免费视频7|
亚洲欧美成人综合久久久|
久久久久免费精品国产|
2021最新久久久视精品爱|
女人高潮久久久叫人喷水|
亚洲欧美成人久久综合中文网|
久久久噜噜噜久久中文字幕色伊伊|
国产99久久久久久免费看|
国产三级精品久久|
精品久久久久久国产三级|
欧美性大战久久久久久|