题目描述:
已知一个斜三角：
22 32 14 77 45
12 34 37 23
44 23 15
34 54
88
从最左上角元素开始往右或往右下走，请问顺着哪条路所经过的值的总和最大，
如可以有路线：22，32，34，23，54 ； 22，12，44，34，88等等
请求出满足值总和最大的那条线路。
View Code
1 void Func(int a[],int n)
2 {
3 int *b = new int[n]; //记录从某个节点开始最大路径上的下一个节点
4 int *c = new int[n]; //记录从某个节点开始最大路径的长度
5 for(int k=0; k<n; k++)
6 {
7 b[k]=c[k]=0;
8 }
9 cout<<"最大路径长度是:"<<MaxWay(a,0,0,b,c)<<endl;//记录最长路径
10 Print(a,b,c);//输出最长路径
11 delete b;
12 delete c;
13 }
14
15 int MaxWay(int a[], int i, int j, int b[], int c[])
16 {
17 int temp=j*(j+1)/2+i;//计算下标 //temp=(10-i)*(i+1)/2+j-5;
18 if(c[temp]!=0)
19 {//若某节点已经求过最大路径则退出，防止重复计算
20 return c[temp];
21 }
22 if(i==4 || j==4)//到达数组边界
23 {
24 b[temp]=-1;
25 c[temp]=a[temp];
26 return a[temp];
27 }
28 int temp1=MaxWay(a,i,j+1,b,c);
29 int temp2=MaxWay(a,i+1,j+1,b,c);
30 if(temp1>temp2)//寻找从当前节点开始最大路径
31 {
32 b[temp]=a[(j+1)*(j+1+1)/2+i];//记录从当前节点开始最大路径上当前节点的下一个节点
33 c[temp]=temp1;//记录从当前节点开始最大路径长度
34 return a[temp]+temp1;
35 }
36 else
37 {
38 b[temp]=a[(j+1)*(j+1+1)/2+i+1];
39 c[temp]=temp2;
40 return a[temp]+temp2;
41 }
42 }
43
44 void Print(int a[],int b[], int c[])
45 {//输出最大路径，从第一个节点开始沿着b中的值输出最长的路径
46 int i=0,j=0;
47 int temp=j*(j+1)/2+i;
48 cout<<"最大路径是:"<<endl;
49 cout<<a[temp]<<" ";
50 while(b[temp]!=-1)
51 {
52 if(b[temp]==a[(j+1)*(j+1+1)/2+i])
53 {
54 cout<<b[temp]<<" ";
55 j++;
56 }
57 else if(b[temp]==a[(j+1)*(j+1+1)/2+i+1])
58 {
59 cout<<b[temp]<<" ";
60 i++;
61 j++;
62 }
63 temp=j*(j+1)/2+i;
64 }
65 cout<<endl;
66 }
67
68 int main()
69 {
70 int a[15]={22,32,12,14,34,44,77,37,23,34,45,23,15,54,88};//以列优先存储上三角矩阵
71 // EnableMemLeakCheck();
72 Func(a,15);
73 return 0;
74 }