数字三角形问题

[效云 李]

Problem B:数字三角形问题
Description
给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形
的顶至底的一条路径，使该路径经过的数字总和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

编程任务：
对于给定的由n 行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数
字和的最大值。
Input
由文件input.txt 提供输入数据。文件的第1 行是数字三角形的行数n，1￡n￡100。接下
来n行是数字三角形各行中的数字。所有数字在0..99之间。
Output
程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是计算
出的最大值。
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30

[效云 李]

VS2005:
// 动态规划-数字三角形问题.cpp : Defines the entry point for the console
application.
//

#include "stdafx.h"
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
void calculate(vector<vector<int> >,vector<vector<int> >&,int);
int max(int,int);

int n=0;
ifstream finput;
finput.open("input.txt");
finput>>n;
vector<vector<int> > v(n+1,vector<int>(n+1));
int i=0,j=0;
int temp=0;
int tag=1;
for(i=1;i<=n;i++)
{
for(j=1;j<=tag;j++)
{
finput>>temp;
v[i][j]=temp;
}
++tag;
}
finput.close();

vector<vector<int> > m(n+1,vector<int>(n+1));
m[1][1]=v[1][1];

calculate(v,m,n);

int result=0;
for(i=1;i<=n;++i)
{
if(result<m[n][i])result=m[n][i];
}

ofstream foutput;
foutput.open("output.txt");
foutput<<result<<endl;
foutput.close();
return 0;
}
void calculate(vector<vector<int> > v,vector<vector<int> >& m,int n)
{
int i=0,j=0;
for(i=2;i<=n;++i)
{
for(j=1;j<=i;j++)
{
if(j==1){m[i][j]=m[i-1][j]+v[i][j];}
else if(j==i){m[i][j]=m[i-1][j-1]+v[i][j];}
else {m[i][j]=max(m[i-1][j-1],m[i-1][j])+v[i][j];}
}
}
}

int max(int a,int b)
{
if(a<b) return b;
else return a;
}

望指教，你们也赶紧啊，赶紧写啊

[zhong nanhai]

不好意思啊，昨天打篮球去了，荒废了一下午。你不错啊，每天做题，厉害！！！

[李效云]

贵在坚持，大家相互激励，都坚持下去！

2009/4/12 zhong nanhai <higerin...@gmail.com>

[zhong nanhai]

对，坚持就是胜利！！！！

[朱涛]

建议将自己 的测试数据和运行结果也发上来（都保存为文本格式），这样方便其他同学的测试和比较。
--

朱涛
中科院软件所基础软件国家工程中心
http://twitter.com/towerjoo

2009/4/12 zhong nanhai <higerin...@gmail.com>

[李效云]

恩，统一输入输出的文本格式好，同意！

2009/4/12 朱涛 <zhutao...@gmail.com>

[higer]

这个题比较简单，用回溯法应该也能做出来。下面是动态规划的做法，VC6.0和gcc 2.95.3-5下测试通过。

/
************************************************************************/
/* 数字三角形问题 */
/
************************************************************************/
#include "stdio.h"
#include <string.h>
int A[101][101];//存放数字三角形的和的最大值
int a[101][101];//存放各值
int path[101][101];//第i行第j个数往上选择的一个数（存放路径）
int calculate(int n,int& k){//计算n行数字三角形
int i=0,j=0;
for(i=1;i<=n;i++){//第i行
for(j=1;j<=i;j++){
A[i][j]=A[i-1][j-1]+a[i][j];
path[i][j]=j-1;
if (A[i][j]<=(A[i-1][j]+a[i][j])) {
A[i][j]=A[i-1][j]+a[i][j];
path[i][j]=j;
}
}
}
int max=A[n][1];
for (i=1;i<=n;i++) {
if (max<=A[n][i]) {
max=A[n][i];
k=i;
}
}
return max;
}
int main(){
memset(a,0,sizeof(a));
memset(A,0,sizeof(A));
memset(path,0,sizeof(path));
int n=0;
scanf("%d",&n);//行数
int i=0,j=0;
for (i=1;i<=n;i++) {//各行数据
for (j=1;j<=i;j++) {
scanf("%d",&a[i][j]);
}
}
int t=0;
printf("%d\n",calculate(n,t));

//打印路径,逆序的
while(n)
{
printf("%d ",t);
t=path[n--][t];
}
return 0;
}