posts - 3,  comments - 4,  trackbacks - 0
设从顶点走到第i层第j个元素的路径和最大值为maxsum[i-1][j-1]
则到第i+1层第j个元素的路径和最大值为max{maxsum[i-1][j-1]+a[i][j],maxsum[i-1][j]+a[i][j]}
而初始条件为maxsum[0] = a[0][0];且maxsum[i][0] = a[0][0]+a[1][0]+...+a[i-1][0]

#include<iostream>
using namespace std;
int main()
{
    
int input[100][100],maxsum[100][100],row,i,j,maxval;
    cin
>>row;

    memset(input,
0,sizeof(int)*10000);
    
for(i=0; i<row; i++)
    {
        
for(j=0;j<=i;j++)
        {
            cin
>>input[i][j];
        }
    }
    memset(maxsum,
0,sizeof(int)*10000);
    maxsum[
0][0= input[0][0];
    
for(i=1;i<row;i++)
    {
        maxsum[i][
0= maxsum[i-1][0+ input[i][0];
        
for(j=1;j<=i;j++)
        {
            
if(maxsum[i-1][j-1]>maxsum[i-1][j])
            {
                maxsum[i][j] 
= maxsum[i-1][j-1+ input[i][j];
            }
            
else
            {
                maxsum[i][j] 
= maxsum[i-1][j] + input[i][j];
            }
        }
    }
    maxval 
= 0;
    
for(i=0;i<row;i++)
    {
        
if(maxval<maxsum[row-1][i])
        {
            maxval 
= maxsum[row-1][i];
        }
    }
    cout
<<maxval<<endl;

    
return 0;
}
posted on 2011-08-19 17:33 成成 阅读(301) 评论(0)  编辑 收藏 引用 所属分类: 算法习题

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理