• <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>
            隨筆 - 62  文章 - 96  trackbacks - 0
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(7)

            隨筆分類(66)

            隨筆檔案(62)

            文章分類(31)

            文章檔案(32)

            友情鏈接

            最新隨筆

            積分與排名

            • 積分 - 235720
            • 排名 - 108

            最新評論

            閱讀排行榜

            評論排行榜

            動態(tài)規(guī)劃即是一個重點,又是一個難點。
            今天終于做出了一題像樣的動態(tài)規(guī)劃題。
            Problem Id:1163??User Id:beyonlin_SCUT
            Memory:100K??Time:0MS
            Language:C++??Result:Accepted
            http://acm.pku.edu.cn/JudgeOnline/problem?id=1163

            The Triangle
            Time Limit:1000MS? Memory Limit:10000K
            Total Submit:3415 Accepted:1988

            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


            分析:
            題意簡化為:
            從第一行開始走到最后一行,每步可以向下走或右下走。
            所求即為從第一行走到最后一行經過的數(shù)總和的最大值。
            令p[][]存儲input。
            5
            7
            3 8
            8 1 0
            2 7 4 4
            |?????\ |? \
            4 5 2 6 5

            如上圖,令i為行,j為列,
            d[i][j]為從第一行走到第i行第j列的最大值。
            對于(i,j)這個點,它可以從不同方向走來,如圖' | '代表從上方走來,' \ '代表從左上方走來。

            則動態(tài)規(guī)則方程為:
            ???????????????? ?{?????d[i-1][1]+p[i][1]???(j=1)
            d[i][j]=Max{???? Max( d[i-1][j-1] , d[i-1][j] ) + p[i][j]???(1<j<i)
            ????????????????? {???? d[i-1][i-1]+p[i][i]???(j=i)

            結果為Max(d[n][j]) , (1<=j<=n)

            代碼如下:

            #include<cstdio>
            int p[100][100];
            int d[100][100];
            int Max(int a,int b)
            {return a>b?a:b;}
            int main()
            {
            	int i,n;
            	scanf("%d",&n);
            	for(i=1;i<=n;i++)
            	{
            		int j;
            		for(j=1;j<=i;j++)
            			scanf("%d",p[i]+j);
            	}
            	d[1][1]=p[1][1];
            	for(i=2;i<=n;i++)
            	{
            		int j;
            		d[i][1]=d[i-1][1]+p[i][1];
            		for(j=2;j<=i;j++)
            			d[i][j]=Max(d[i-1][j-1],d[i-1][j])+p[i][j];
            		d[i][i]=d[i-1][i-1]+p[i][i];
            	}
            	int max=0;
            	for(i=1;i<=n;i++)
            	{
            		if(d[n][i]>max)
            			max=d[n][i];
            	}
            	printf("%d\n",max);
            	return 0;
            }
            

            posted on 2006-08-28 10:31 beyonlin 閱讀(599) 評論(2)  編輯 收藏 引用 所屬分類: acm之路

            FeedBack:
            # re: 我的動態(tài)規(guī)劃啟蒙題 2006-08-28 16:02 
            嘿嘿, 這也是我的第一題動態(tài)規(guī)劃野~~~~  回復  更多評論
              
            # re: 我的動態(tài)規(guī)劃啟蒙題 2008-10-28 14:43 東·德
            祝賀!我也剛剛看懂,但是加上“一條路徑”的輸出就更好了。是吧  回復  更多評論
              
            精品久久久久久无码免费| 亚洲精品NV久久久久久久久久| 久久国产欧美日韩精品| 99久久精品免费看国产一区二区三区| 五月丁香综合激情六月久久| 99久久精品影院老鸭窝| 日韩十八禁一区二区久久 | 综合久久精品色| 久久这里的只有是精品23| 一本久久精品一区二区| 亚洲人成网亚洲欧洲无码久久| 久久99国产亚洲高清观看首页| 国产精品毛片久久久久久久| 国产激情久久久久影院老熟女免费 | 久久国产免费观看精品| 欧美精品九九99久久在观看| 久久久久久亚洲Av无码精品专口| 精品久久久久久国产免费了| 亚洲AV无一区二区三区久久 | 狠狠久久综合伊人不卡| 色综合久久久久无码专区 | 久久久久亚洲AV无码麻豆| 久久99精品久久久久久齐齐| 一本一道久久综合狠狠老| 久久久久久极精品久久久| 国产一久久香蕉国产线看观看| 狠狠色丁香久久婷婷综合图片| 国产一久久香蕉国产线看观看| 伊人 久久 精品| 久久久久女教师免费一区| 91精品国产乱码久久久久久| 精品久久久一二三区| 久久久久一级精品亚洲国产成人综合AV区| 精品综合久久久久久888蜜芽| 亚洲日韩中文无码久久| 国产精品久久久久免费a∨| 亚洲乱码日产精品a级毛片久久| 久久精品国产精品亚洲人人| 久久99亚洲综合精品首页| 久久久久久噜噜精品免费直播| 久久乐国产精品亚洲综合|