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

    
            

            




            







												


        




            
	
		


            隨筆 - 87 
文章 - 279 
trackbacks - 0


             
	

            

            
	
		
            
			
            
	
            
		
            <2006年3月>
            
	
            日一二三四五六
            2627281234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678
            

            

            
			


            
	潛心看書研究！

            

			

            常用鏈接
            


            留言簿(19)
            




		
            隨筆分類(81)
            
		
				
			
	
		
            文章分類(89)
            
		
				
			
	
		
            相冊(cè)
            
		
				
			
	
		
            ACM OJ
            
		
				
			
	
		
            My friends
            
		
				
			
	




            搜索
            

              
	
            • 
		
            •  
	
              • 

            


            積分與排名
            

              
	
            • 
		積分 -
		218070
	
            • 
		排名 -
		117
	
              • 

            


            最新評(píng)論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評(píng)論排行榜
            


            		
	

            

            
	
					


            
	
	
            The Triangle 
            Time Limit:1000MS  Memory Limit:10000K
            

            Description
            

            7

            3   8

            8   1   0

            2   7   4   4

            4   5   2   6   5

            

            (Figure 1)

            Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right. 
            

            

            Input
            Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99. 
            

            Output
            Your program is to write to standard output. The highest sum is written as an integer.
            

            Sample Input
            5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5
            

            

            Sample Output
            30
            

            

            Source
            IOI 1994
            

            #include<iostream>
            using namespace std;

            int main()
            {
                            int n,digital_num;
                            int result[100][100];
                            int *num;
                            int max = 0;
                            int i,j;
                cin            >>n;
                digital_num             = n;
                num             = new int[digital_num];

                            for (i = 0; i<n; i++)
                            {
                                for (j = 0; j<=i; j++)
                                {
                        cin            >>num[j];
                                    if (i==0)
                            result[i][j]             = num[j];
                                    if (i>0)
                                    {
                                        if (j==0)
                                result[i][j]             = result[i-1][j]+num[j];
                                        if (j==i)
                                result[i][j]             = result[i-1][j-1]+num[j];
                                        if (j>0&&j<i)
                                        {
                                           if (result[i-1][j]>result[i-1][j-1])
                                   result[i][j]             = result[i-1][j]+num[j];
                                           else
                                   result[i][j]             = result[i-1][j-1]+num[j];
                            }
                        }
                    }
                }
                
                            for (i = 0; i<n; i++)
                                if (result[n-1][i]>max)
                        max             = result[n-1][i];

                cout            <<max<<endl;
                            return 0;
            }
            上面是通過的原程序。140k,15MS。


            這道題目，過得好辛苦，從開始的遞歸，到遞推加回溯，到窮舉，到窮舉加剪枝，結(jié)果就從TLE->TLE->TLE->WA.  一直用著要保留路徑的方法，所以怎么也做不出來(lái)，后來(lái)?yè)Q了個(gè)思維角度，保存每一步的結(jié)果，動(dòng)態(tài)規(guī)劃，終于就AC了。做了這題，另我復(fù)習(xí)了好幾種方法，也對(duì)DP有了深得認(rèn)識(shí)，可以說這是搞競(jìng)賽的好題目，經(jīng)典，推薦！！
	
            posted on 2006-02-21 13:09 豪 閱讀(1609) 評(píng)論(6)  編輯 收藏 引用  所屬分類: 算法&ACM 
            

            







            
	    
    


            
FeedBack:

            
	

		
            
			
            
			
            # re: 終于做出了一題IOI了，有點(diǎn)心得。 2006-02-21 20:58 豪
            
				
            又忘記 delete []num 了！~~  回復(fù)  更多評(píng)論
              
			
            
		
            
	
		
            
			
            
			
            # re: 終于做出了一題IOI了，有點(diǎn)心得。 2006-02-25 09:29 imlazy
            
				
            加油。  回復(fù)  更多評(píng)論
              
			
            
		
            
	
		
            
			
            
			
            # re: 終于做出了一題IOI了，有點(diǎn)心得。 2006-03-11 11:01 空明流轉(zhuǎn)
            
				
            很好啊，再接再厲！

            我的動(dòng)態(tài)規(guī)劃一直學(xué)的不好。。。  回復(fù)  更多評(píng)論
              
			
            
		
            
	
		
            
			
            
			
            # re: 終于做出了一題IOI了，有點(diǎn)心得。 2006-03-12 11:09 豪
            
				
            感謝 空明流轉(zhuǎn) 的支持!

            我已經(jīng)領(lǐng)略到acm的恐怖了,但是我不會(huì)輕易放棄的:)  回復(fù)  更多評(píng)論
              
			
            
		
            
	
		
            
			
            
			
            # re: 終于做出了一題IOI了，有點(diǎn)心得。 2006-08-12 21:15 Optimistic
            
				
            加油！  回復(fù)  更多評(píng)論
              
			
            
		
            
	
		
            
			
            
			
            # re: 終于做出了一題IOI了，有點(diǎn)心得。 2007-05-03 00:27 App
            
				
            inline int calpos(int row,int col)

            {

            

            	return row*(row-1)/2+col;

            }

            int tmem[5051]={-1,7,3,8,8,1,0,2,7,4,4,4,5,2,6,5};

            int bestroute[5051]={-1};

            int height=5;

            

            int highestroute(int row,int col)

            {

            	if (row>height)

            	{

            		return 0;

            	}

            	int pos=calpos(row,col);

            

            	if (bestroute[pos]>0)

            	{

            		return bestroute[pos];

            	}

            	int nr[]={1,0,1,1};

            	int max=0;

            	int i;

            	for (i=0;i<4;i+=2)

            	{

            		int tmp=highestroute(row+nr[i],col+nr[i+1]);

            		if (tmp>max)

            		{

            			max=tmp;

            		}

            	}

            	max+=tmem[pos];

            	bestroute[pos]=max;

            	return max;

            }

            亂寫的，感覺遞歸邏輯更加清晰:-)  回復(fù)  更多評(píng)論
              
			
            
		
            
	




            






            

				
	



            


    
    







	   
	



久久精品国产久精国产|
91精品国产综合久久香蕉|
性欧美丰满熟妇XXXX性久久久
|
久久国产精品无|
亚洲国产精品无码久久久蜜芽
|
欧美亚洲国产精品久久|
国产精品久久久久影视不卡|
久久人妻少妇嫩草AV蜜桃|
亚洲午夜久久久影院伊人|
国产精品欧美久久久久天天影视
|
精品综合久久久久久97超人
|
久久亚洲国产精品123区|
久久久噜噜噜www成人网|
久久99精品久久久久久野外|
亚洲AV日韩AV天堂久久|
三级片免费观看久久|
97超级碰碰碰碰久久久久|
亚洲精品美女久久久久99|
久久亚洲国产成人精品无码区|
久久久久人妻一区精品性色av|
99久久国产亚洲综合精品|
国产免费久久精品99久久|
www.久久热|
久久精品国产影库免费看|
日产精品久久久久久久性色|
国产免费久久精品99re丫y|
国产一区二区三精品久久久无广告
|
97r久久精品国产99国产精|
狠狠综合久久综合88亚洲|
怡红院日本一道日本久久
|
99麻豆久久久国产精品免费|
亚洲愉拍99热成人精品热久久|
伊人久久亚洲综合影院|
亚洲午夜无码AV毛片久久|
一本久道久久综合狠狠躁AV|
欧美激情精品久久久久久久|
久久久久女教师免费一区|
国内精品伊人久久久久影院对白
|
久久中文字幕一区二区|
99久久综合国产精品二区|
久久国产乱子伦精品免费午夜|