• <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年2月>
            
	
            日一二三四五六
            2930311234
            567891011
            12131415161718
            19202122232425
            2627281234
            567891011
            

            

            
			


            
	潛心看書研究！

            

			

            常用鏈接
            


            留言簿(19)
            




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




            搜索
            

              
	
            • 
		
            •  
	
              • 

            


            積分與排名
            

              
	
            • 
		積分 -
		217813
	
            • 
		排名 -
		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。


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

            







            
	    
    


            
FeedBack:

            
	

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

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

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

            }

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




            






            

				
	



            


    
    







	   
	



天堂久久天堂AV色综合|
A级毛片无码久久精品免费
|
亚洲中文字幕无码久久2017|
久久国产亚洲精品无码|
亚洲AV无码久久|
国产午夜福利精品久久|
蜜臀久久99精品久久久久久小说
|
久久久久人妻精品一区|
99久久婷婷国产综合精品草原|
久久久久亚洲AV成人片|
一本色道久久88加勒比—综合|
无码国内精品久久人妻蜜桃|
久久精品国产亚洲AV嫖农村妇女|
久久人人爽人人澡人人高潮AV|
蜜臀av性久久久久蜜臀aⅴ麻豆
|
亚洲AV成人无码久久精品老人|
国产女人aaa级久久久级|
久久影视综合亚洲|
91精品国产乱码久久久久久|
亚洲欧洲久久久精品|
国产亚洲精久久久久久无码|
思思久久好好热精品国产|
99久久人妻无码精品系列|
久久久久久久91精品免费观看|
性高湖久久久久久久久|
久久天天躁狠狠躁夜夜2020老熟妇
|
久久久久99精品成人片三人毛片|
丰满少妇高潮惨叫久久久|
伊人久久大香线蕉av不变影院|
久久人人爽人爽人人爽av|
国产精品日韩深夜福利久久|
色偷偷偷久久伊人大杳蕉|
色综合久久久久网|
无码AV波多野结衣久久|
综合久久给合久久狠狠狠97色|
亚洲乱码精品久久久久..|
亚洲欧洲中文日韩久久AV乱码|
韩国三级大全久久网站|
久久99精品久久只有精品|
久久天堂AV综合合色蜜桃网|
77777亚洲午夜久久多人|