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




            






            

				
	



            


    
    







	   
	



2021国产成人精品久久|
久久免费大片|
狠狠狠色丁香婷婷综合久久五月|
国产三级久久久精品麻豆三级
|
精品久久久久久久久久中文字幕
|
国产产无码乱码精品久久鸭|
青青国产成人久久91网|
久久大香萑太香蕉av|
91精品国产综合久久婷婷
|
国内精品九九久久久精品|
国产午夜精品理论片久久|
一本色综合网久久|
久久久久国产一级毛片高清板
|
国产精品福利一区二区久久|
无码国内精品久久人妻麻豆按摩|
久久久国产精华液|
国产精品免费久久久久影院|
少妇无套内谢久久久久|
久久91精品综合国产首页|
国产亚洲欧美精品久久久|
久久精品国产色蜜蜜麻豆|
久久久久国产精品麻豆AR影院|
91久久国产视频|
成人资源影音先锋久久资源网|
国内精品人妻无码久久久影院导航
|
久久久久97国产精华液好用吗|
久久亚洲精品视频|
国产一久久香蕉国产线看观看
|
久久精品极品盛宴观看|
国内精品久久久久久中文字幕|
日本久久久精品中文字幕|
a级成人毛片久久|
国产成人久久激情91|
国产精品久久久久国产A级|
久久精品国产亚洲精品2020|
久久综合给合久久狠狠狠97色|
亚洲精品无码久久久久久|
人妻丰满AV无码久久不卡|
无码人妻精品一区二区三区久久久
|
久久精品国产99国产电影网|
99久久人妻无码精品系列蜜桃|