• <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 東·德
            祝賀!我也剛剛看懂,但是加上“一條路徑”的輸出就更好了。是吧  回復  更多評論
              
            一级a性色生活片久久无| 99精品久久精品一区二区| 色婷婷综合久久久久中文| 久久无码精品一区二区三区| 精品久久久久久99人妻| 99久久婷婷国产一区二区| 99久久国产综合精品五月天喷水| 国产∨亚洲V天堂无码久久久| 久久综合给合久久狠狠狠97色| 久久婷婷五月综合国产尤物app| 亚洲中文字幕无码久久2017| 欧美亚洲色综久久精品国产| 国内精品伊人久久久久av一坑| 天天爽天天狠久久久综合麻豆| 日韩av无码久久精品免费| 国产精品国色综合久久| 亚洲国产精品久久久久婷婷软件 | 久久精品亚洲AV久久久无码| 日本久久久久久久久久| 97精品依人久久久大香线蕉97| 亚洲va国产va天堂va久久| 久久电影网一区| 久久久综合香蕉尹人综合网| 亚洲国产成人精品91久久久| 欧美亚洲国产精品久久| 国内精品久久久久影院优| 国产精品日韩深夜福利久久| 精品熟女少妇AV免费久久| 精品久久久久久国产潘金莲| 精品久久久久久无码中文野结衣 | 99久久精品免费观看国产| 久久综合色之久久综合| 久久无码人妻一区二区三区| 亚洲成人精品久久| 久久国产欧美日韩精品| 国产成人久久精品麻豆一区| 亚洲人成网亚洲欧洲无码久久| 四虎国产精品免费久久久| 亚洲国产精品高清久久久| 99久久人人爽亚洲精品美女| 无码日韩人妻精品久久蜜桃|