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


             
	

            

            
	
		
            
			
            
	
            
		
            <2025年6月>
            
	
            日一二三四五六
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345
            

            

            
			


            
	潛心看書研究！

            

			

            常用鏈接
            


            留言簿(19)
            




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




            搜索
            

              
	
            • 
		
            •  
	
              • 

            


            積分與排名
            

              
	
            • 
		積分 -
		217765
	
            • 
		排名 -
		117
	
              • 

            


            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


            		
	

            

            
	
					


            
	
	
            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。


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

            







            
	    
    


            
FeedBack:

            
	

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

            我的動態規劃一直學的不好。。。  回復  更多評論
              
			
            
		
            
	
		
            
			
            
			
            # re: 終于做出了一題IOI了，有點心得。 2006-03-12 11:09 豪
            
				
            感謝 空明流轉 的支持!

            我已經領略到acm的恐怖了,但是我不會輕易放棄的:)  回復  更多評論
              
			
            
		
            
	
		
            
			
            
			
            # re: 終于做出了一題IOI了，有點心得。 2006-08-12 21:15 Optimistic
            
				
            加油！  回復  更多評論
              
			
            
		
            
	
		
            
			
            
			
            # re: 終于做出了一題IOI了，有點心得。 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;

            }

            亂寫的，感覺遞歸邏輯更加清晰:-)  回復  更多評論
              
			
            
		
            
	




            






            

				
	



            


    
    







	   
	



日本久久久久久中文字幕|
久久综合狠狠综合久久97色|
久久久久国产精品人妻|
中文字幕人妻色偷偷久久|
精品国产乱码久久久久久1区2区
|
97久久精品人人澡人人爽|
国产精品免费久久久久久久久|
亚洲国产成人久久综合一区77|
亚洲午夜久久久久久久久电影网|
久久99国产精品久久99|
久久久久se色偷偷亚洲精品av|
久久91亚洲人成电影网站|
中文字幕无码久久精品青草|
久久91综合国产91久久精品|
久久精品国产99国产精品导航|
91麻豆精品国产91久久久久久|
人妻无码αv中文字幕久久琪琪布|
国产午夜精品理论片久久|
蜜臀av性久久久久蜜臀aⅴ麻豆|
久久免费视频6|
国产精品九九久久免费视频|
久久国产精品一国产精品金尊
|
久久天堂AV综合合色蜜桃网|
久久人妻少妇嫩草AV无码蜜桃|
国产精品久久久久无码av|
亚洲va久久久噜噜噜久久狠狠|
无码乱码观看精品久久|
久久久久久国产精品美女|
日韩亚洲欧美久久久www综合网
|
国内精品久久久久影院优|
久久九九兔免费精品6|
亚洲第一永久AV网站久久精品男人的天堂AV
|
午夜天堂精品久久久久|
久久青青色综合|
久久久久久久久66精品片|
精品久久综合1区2区3区激情|
久久香蕉国产线看观看99|
欧美一区二区精品久久|
91久久精品国产成人久久|
亚洲一区中文字幕久久|
99久久国产综合精品网成人影院
|