鱼C论坛

 找回密码
 立即注册
查看: 3679|回复: 15

题目18:找出从三角形顶端走到底端的最大和

[复制链接]
发表于 2015-4-21 16:51:42 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
Maximum path sum I

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

BaiduShurufa_2015-4-21_16-48-14.png

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

BaiduShurufa_2015-4-21_16-48-30.png

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

题目:

从下面的三角形的顶端开始,向下面一行的相邻数字移动,从顶端到底端的最大总和为 23.

BaiduShurufa_2015-4-21_16-49-50.png

也就是 3 + 7 + 4 + 9 = 23.

找出从以下三角形的顶端走到底端的最大总和:

BaiduShurufa_2015-4-21_16-50-39.png

评分

参与人数 1贡献 +1 收起 理由
cwhsmile + 1 1074,用时0.02s,用倒推保留最大值方法

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-7-3 02:09:25 | 显示全部楼层
本帖最后由 huomqh 于 2016-7-3 02:20 编辑
  1. def f(r,c,sss,link):
  2.     if r==14:
  3.         y=[sss,link]
  4.         k.append(y)
  5.         return 1
  6.     else:
  7.         f(r+1,c,sss+a[r+1][c],link+"+"+str(c))
  8.         f(r+1,c+1,sss+a[r+1][c+1],link+"+"+str(c+1))
  9.    
  10.         


  11. a=[[75],[95,64],[17,47,82],[18,35,87,10],[20,4,82,47,65],[19,1,23,75,3,34],[88,2,77,73,7,63,67],[99,65,4,28,6,16,70,92],[41,41,26,56,83,40,80,70,33],[41,48,72,33,47,32,37,16,94,29],[53,71,44,65,25,43,91,52,97,51,14],[70,11,33,28,77,73,17,78,39,68,17,57],[91,71,52,38,17,14,91,43,58,50,27,29,48],[63,66,4,68,89,53,67,30,73,16,69,87,40,31],[4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]
  12. k=[]
  13. result=[]
  14. f(0,0,a[0][0],'0')
  15. m=0
  16. for i in k:
  17.    if i[0]>m:
  18.        m=i[0]
  19.        result=i[:]
  20. print (result[0])
  21. b=result[1].split("+")
  22. l=str(a[0][0])
  23. for z in range(1,len(b)):
  24.     l=l+"+"+str(a[z][int(b[z])])
  25. print(l)
  26.    
复制代码
这次应该对了
1074
75+64+82+87+82+75+73+28+83+32+91+78+58+73+93
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-7-3 02:10:13 | 显示全部楼层
本帖最后由 huomqh 于 2016-7-3 02:40 编辑



随便写写的,可读性很差,大家见谅。
附一张分布图吧

                               
登录/注册后可看大图
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-8-27 14:21:03 | 显示全部楼层
  1. a=[[4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23],
  2.    [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
  3.    [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
  4.    [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
  5.    [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
  6.    [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
  7.    [41, 41, 26, 56, 83, 40, 80, 70, 33],
  8.    [99, 65, 4, 28, 6, 16, 70, 92],
  9.    [88, 2, 77, 73, 7, 63, 67],
  10.    [19, 1, 23, 75, 3, 34],
  11.    [20, 4, 82, 47, 65],
  12.    [18, 35, 87, 10],
  13.    [17, 47, 82],
  14.    [95, 64],
  15.    [75]]
  16. for i in range(1,15):
  17.     for j in range(15-i):
  18.         if a[i-1][j] < a[i-1][j+1]:
  19.             a[i][j] = a[i][j]+a[i-1][j+1]
  20.         else:
  21.             a[i][j] = a[i][j]+a[i-1][j]

  22. print(a[14][0])
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-8-28 12:25:04 | 显示全部楼层
1074 应该是吧。。
  1. #include <iostream>
  2. using namespace std;
  3. int myMaxNumber = 0;
  4. /* 数组线性保存 */
  5. int myArry[]={
  6.         75,
  7.         95,64,
  8.         17,47,82,
  9.         18,35,87,10,
  10.         20,04,82,47,65,
  11.         19,01,23,75,03,34,
  12.         88,02,77,73,07,63,67,
  13.         99,65,04,28,06,16,70,92,
  14.         41,41,26,56,83,40,80,70,33,
  15.         41,48,72,33,47,32,37,16,94,29,
  16.         53,71,44,65,25,43,91,52,97,51,14,
  17.         70,11,33,28,77,73,17,78,39,68,17,57,
  18.         91,71,52,38,17,14,91,43,58,50,27,29,48,
  19.         63,66,04,68,89,53,67,30,73,16,69,87,40,31,
  20.         04,62,98,27,23,9,70,98,73,93,38,53,60,04,23

  21.         };
  22. int myArry2[]={3,7,4,2,4,6,8,5,9,3};

  23. /* 获取第h行第1个数 */
  24. /*  递归关系 f(1) = 1  f(x) = f(x-1) + 1 */
  25. int getNumber(int h)
  26. {
  27.         int n = 0;
  28.         if(1==h)
  29.         {
  30.                 return 1;
  31.         }
  32.          n = getNumber(h-1);
  33.         return n+(h-1);
  34. }
  35. int getNum(int h,int l)
  36. {
  37.         return myArry[getNumber(h)+l-2];
  38. }
  39. int getMaxNum(int l,int h,int result)
  40. {
  41.         int j,k;
  42.         j = l;
  43.         k = l + 1;
  44.         //如果到达最底层  算出结果
  45.         if( 15 == h )
  46.         {
  47.                 int a = result + getNum(h,l);
  48.                 if( myMaxNumber < a)
  49.                 {
  50.                         myMaxNumber = a;
  51.                 }
  52.                 return a;
  53.         }

  54.         /* 接着上一层的开始  */
  55.         getMaxNum(j,h+1,result+getNum(h,l));
  56.         getMaxNum(k,h+1,result+getNum(h,l));
  57. }
  58. int main(void)
  59. {
  60.         getMaxNum(1,1,0);
  61.         std::cout<<myMaxNumber;
  62.         return 0;
  63. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-1-18 15:59:58 | 显示全部楼层
此代码使用matlab编程
Problem18所用时间为2.0008秒
Problem18的答案为1074
  1. %题目18:找出从三角形顶端走到底端的最大和
  2. %本质上是二叉树
  3. function Output=Problem18(Input)
  4. tic
  5. if nargin==0
  6.   Input=[75,zeros(1,14);...
  7.          95,64,zeros(1,13);...
  8.          17,47,82,zeros(1,12);...
  9.          18,35,87,10,zeros(1,11);...
  10.          20,04,82,47,65,zeros(1,10);...
  11.          19,01,23,75,03,34,zeros(1,9);...
  12.          88,02,77,73,07,63,67,zeros(1,8);...
  13.          99,65,04,28,06,16,70,92,zeros(1,7);...
  14.          41,41,26,56,83,40,80,70,33,zeros(1,6);...
  15.          41,48,72,33,47,32,37,16,94,29,zeros(1,5);...
  16.          53,71,44,65,25,43,91,52,97,51,14,zeros(1,4);...
  17.          70,11,33,28,77,73,17,78,39,68,17,57,zeros(1,3);...
  18.          91,71,52,38,17,14,91,43,58,50,27,29,48,zeros(1,2);...
  19.          63,66,04,68,89,53,67,30,73,16,69,87,40,31,zeros(1,1);...
  20.          04,62,98,27,23,9,70,98,73,93,38,53,60,04,23];
  21. end
  22. Pro=2^(length(Input(1,:))-1);%有多少种可能
  23. A=Input;
  24. L=length(Input(1,:))-1;
  25. Result=0;
  26. for ii=1:Pro
  27.     V=Get2bit(ii-1,L);%V=Vector,一个数二进制表示的向量
  28.     Sum=A(1,1);
  29.     for jj=1:L
  30.         Sum=Sum+A(jj+1,1+sum(V(1:jj)));
  31.     end
  32.     if Sum>Result
  33.         Result=Sum;
  34.     end
  35. end
  36. toc
  37. Output=Result;
  38. disp('此代码使用matlab编程')
  39. disp(['Problem18所用时间为',num2str(toc),'秒'])
  40. disp(['Problem18的答案为',num2str(Output)])
  41. end
  42. %% 子程序
  43. %输入一个数Input,得到其二进制表示,L为期长度
  44. function Output=Get2bit(Input,L)
  45. if nargin==0
  46. L=14;
  47. Input=56;
  48. end
  49. Temp=Input;
  50. Rank=[];
  51. while (Temp>=1)
  52.     Rank_Temp=[Rank,mod(Temp,2)];
  53.     Rank=Rank_Temp;
  54.     Temp=floor(Temp/2);
  55. end
  56. if length(Rank)<L
  57.     Output=[Rank,zeros(1,L-length(Rank))];
  58. else
  59.     Output=Rank;
  60. end
  61. end
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-21 10:09:24 | 显示全部楼层
  1. temp = '''75
  2. 95 64
  3. 17 47 82
  4. 18 35 87 10
  5. 20 04 82 47 65
  6. 19 01 23 75 03 34
  7. 88 02 77 73 07 63 67
  8. 99 65 04 28 06 16 70 92
  9. 41 41 26 56 83 40 80 70 33
  10. 41 48 72 33 47 32 37 16 94 29
  11. 53 71 44 65 25 43 91 52 97 51 14
  12. 70 11 33 28 77 73 17 78 39 68 17 57
  13. 91 71 52 38 17 14 91 43 58 50 27 29 48
  14. 63 66 04 68 89 53 67 30 73 16 69 87 40 31
  15. 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''

  16. temp = [i.split(' ') for i in temp.split('\n')]

  17. for i in range(len(temp) - 2, -1, -1):
  18.     for j in range(len(temp[i])):
  19.         temp[i][j] = max(int(temp[i][j]) + int(temp[i + 1][j]), int(temp[i][j]) + int(temp[i + 1][j + 1]))
  20.     print temp[i]
复制代码

从下往上算比较高效,此代码适用于第67题,只要把上面的数字替换即可。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-6-28 20:10:00 | 显示全部楼层
  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4. int max1=0;
  5. int map[16][16]={
  6.         {00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00},
  7.         {00,75,00,00,00,00,00,00,00,00,00,00,00,00,00,00},
  8.         {00,95,64,00,00,00,00,00,00,00,00,00,00,00,00,00},
  9.         {00,17,47,82,00,00,00,00,00,00,00,00,00,00,00,00},
  10.         {00,18,35,87,10,00,00,00,00,00,00,00,00,00,00,00},
  11.         {00,20, 4,82,47,65,00,00,00,00,00,00,00,00,00,00},
  12.         {00,19, 1,23,75, 3,34,00,00,00,00,00,00,00,00,00},
  13.         {00,88, 2,77,73, 7,63,67,00,00,00,00,00,00,00,00},
  14.         {00,99,65, 4,28, 6,16,70,92,00,00,00,00,00,00,00},
  15.         {00,41,41,26,56,83,40,80,70,33,00,00,00,00,00,00},
  16.         {00,41,48,72,33,47,32,37,16,94,29,00,00,00,00,00},
  17.         {00,53,71,44,65,25,43,91,52,97,51,14,00,00,00,00},
  18.         {00,70,11,33,28,77,73,17,78,39,68,17,57,00,00,00},
  19.         {00,91,71,52,38,17,14,91,43,58,50,27,29,48,00,00},
  20.         {00,63,66, 4,68,89,53,67,30,73,16,69,87,40,31,00},
  21.         {00, 4,62,98,27,23, 9,70,98,73,93,38,53,60, 4,23}
  22. };
  23. void count(int x,int y,int sum)
  24. {
  25.         if(y==16)
  26.         {
  27.                 max1=max(max1,sum);
  28.         }
  29.         else
  30.         {
  31.                 sum+=map[y][x];
  32.                 count(x,y+1,sum);
  33.                 count(x+1,y+1,sum);
  34.         }
  35. }

  36. int main()
  37. {
  38.         count(1,1,0);
  39.         cout<<"最大的和是:"<<max1;
  40. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-15 20:18:26 | 显示全部楼层
python3 用时0.000216秒
结果是1074, 75, 64, 82, 87, 82, 75, 73, 28, 83, 32, 91, 78, 58, 73, 93
  1. import time

  2. start = time.clock()
  3. nums = [[75],
  4.         [95, 64],
  5.         [17, 47, 82],
  6.         [18, 35, 87, 10],
  7.         [20, 4, 82, 47, 65],
  8.         [19, 1, 23, 75, 3, 34],
  9.         [88, 2, 77, 73, 7, 63, 67],
  10.         [99, 65, 4, 28, 6, 16, 70, 92],
  11.         [41, 41, 26, 56, 83, 40, 80, 70, 33],
  12.         [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
  13.         [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
  14.         [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
  15.         [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
  16.         [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
  17.         [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]]

  18. lens = len(nums)
  19. biglist = []
  20. for i in range(lens):
  21.     biglist += [[nums[lens - 1][i], nums[lens - 1][i]]]

  22. for i in range(lens - 1):
  23.     temp = biglist
  24.     n = lens - 2 - i
  25.     biglist = []
  26.     for j in range(n + 1):
  27.         tempn = nums[n][j]
  28.         if temp[j][0] > temp[j + 1][0]:
  29.             biglist += [[tempn + temp[j][0]] + [tempn] + temp[j][1:]]
  30.         else:
  31.             biglist += [[tempn + temp[j + 1][0]] + [tempn] + temp[j + 1][1:]]
  32. print(biglist[0])

  33. end = time.clock()
  34. print("read:%f s" % (end - start))
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-4-25 23:57:08 | 显示全部楼层
  1. import time
  2. import math

  3. def test1():
  4.     nums = [[75],
  5.         [95, 64],
  6.         [17, 47, 82],
  7.         [18, 35, 87, 10],
  8.         [20, 4, 82, 47, 65],
  9.         [19, 1, 23, 75, 3, 34],
  10.         [88, 2, 77, 73, 7, 63, 67],
  11.         [99, 65, 4, 28, 6, 16, 70, 92],
  12.         [41, 41, 26, 56, 83, 40, 80, 70, 33],
  13.         [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
  14.         [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
  15.         [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
  16.         [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
  17.         [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
  18.         [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]]
  19.     last_len = len(nums[-1])
  20.     nums = nums[::-1]
  21.     li = nums[0]
  22.    
  23.     for i in range(1,last_len):
  24.         new = li[:]
  25.         li = []
  26.         for j in range(len(nums[i])):
  27.             front = nums[i][j] + new[j]
  28.             #print(front,end=',')
  29.             rear = nums[i][j] + new[j+1]
  30.             #print(rear)
  31.             if front > rear:
  32.                 li.append(front)
  33.             else:
  34.                 li.append(rear)
  35.         #print(li)
  36.     new = li[:]

  37.    
  38.     return max(new)



  39. start = time.perf_counter()
  40. print(test1())
  41. end = time.perf_counter()
  42. print(end-start)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-5-29 23:43:14 | 显示全部楼层
  1. import time as t
  2. start = t.perf_counter()
  3. a=[[75],
  4.    [95,64],
  5.    [17,47,82],
  6.    [18,35,87,10],
  7.    [20,4,82,47,65],
  8.    [19,1,23,75,3,34],
  9.    [88,2,77,73,7,63,67],
  10.    [99,65,4,28,6,16,70,92],
  11.    [41,41,26,56,83,40,80,70,33],
  12.    [41,48,72,33,47,32,37,16,94,29],
  13.    [53,71,44,65,25,43,91,52,97,51,14],
  14.    [70,11,33,28,77,73,17,78,39,68,17,57],
  15.    [91,71,52,38,17,14,91,43,58,50,27,29,48],
  16.    [63,66,4,68,89,53,67,30,73,16,69,87,40,31],
  17.    [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]
  18. for i in range(14,-1,-1):
  19.    for j in range(i):
  20.       if a[i][j]>a[i][j+1]:
  21.          a[i-1][j] += a[i][j]
  22.       else:
  23.          a[i - 1][j] += a[i][j+1]
  24. print(a[0][0])
  25. end = t.perf_counter()
  26. print(end-start)
复制代码

1074
8.210900000000035e-05
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-29 18:37:01 | 显示全部楼层
C++ 0ms
  1. #include<iostream>
  2. using namespace std;
  3. #define max(a,b) (a>b?a:b)


  4. int main() {
  5.     char i = 14, j;
  6.     int arr[15][15] = {
  7.         {75},
  8.         {95, 64},
  9.         {17, 47, 82},
  10.         {18, 35, 87, 10},
  11.         {20, 04, 82, 47, 65},
  12.         {19, 01, 23, 75, 03, 34},
  13.         {88, 02, 77, 73, 07, 63, 67},
  14.         {99, 65, 04, 28, 06, 16, 70, 92},
  15.         {41, 41, 26, 56, 83, 40, 80, 70, 33},
  16.         {41, 48, 72, 33, 47, 32, 37, 16, 94, 29},
  17.         {53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14},
  18.         {70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57},
  19.         {91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48},
  20.         {63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31},
  21.         {04, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 04, 23}
  22.     };

  23.     while (j = i--) {
  24.         while (j--) {
  25.             arr[i][j] += max(arr[i + 1][j], arr[i + 1][j + 1]);
  26.         }
  27.     }

  28.     cout << arr[0][0] << endl;
  29.     return 0;
  30. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-6-30 17:23:53 | 显示全部楼层
本帖最后由 永恒的蓝色梦想 于 2020-6-30 17:59 编辑

我不知道错在哪里,为什么大家的答案都是1074,我算的是1064

  1. #include<stdio.h>
  2. #include<stdlib.h>

  3. #define N 15

  4. void main()
  5. {
  6.         int a[N][N] = { {75},
  7.                                         {95,64},
  8.                                         {17,47,82},
  9.                                         {18,35,87,10},
  10.                                         {20,4,82,47,65},
  11.                                         {19,1,23,75,3,34},
  12.                                         {88,2,77,73,7,63,67},
  13.                                         {99,65,4,28,6,16,70,92},
  14.                                         {41,41,26,56,83,40,80,70,33},
  15.                                         {41,48,72,33,47,32,37,16,94,29},
  16.                                         {53,71,44,65,25,43,91,52,97,51,14},
  17.                                         {70,11,33,28,77,73,17,78,39,68,17,57},
  18.                                         {91,71,52,38,17,14,91,43,58,50,27,29,48},
  19.                                         {63,66,4,68,89,53,67,30,73,16,69,87,40,31},
  20.                                         {4,62,98,27,23,9,70,98,73,93,38,53,60,4,23} };

  21.         for (int i = 0; i < N; i++)//打印三角形
  22.         {
  23.                 printf("%*d", 45 - 3 * i, a[i][0]);
  24.                 for (int j = 1; j <= i; j++)
  25.                 {
  26.                         printf("%6d", a[i][j]);
  27.                 }
  28.                 printf("\n");
  29.         }

  30.         int k = 1;
  31.         int nums[15] = { 0 };
  32.         int t = 0;
  33.         nums[0] = a[0][0];
  34.         int res = 0;
  35.         while (k < N)
  36.         {
  37.                 if (a[k][t] > a[k][t + 1])
  38.                 {
  39.                         nums[k] = a[k][t];
  40.                 }
  41.                 else
  42.                 {
  43.                         nums[k] = a[k][t + 1];
  44.                         t = t + 1;
  45.                 }
  46.                 k++;
  47.         }
  48.         printf("产生的序列是\n");
  49.         for (int i = 0; i < N; i++)
  50.         {
  51.                 printf("%4d", nums[i]);
  52.         }
  53.         printf("\n");
  54.         for (int i = 0; i < N; i++)
  55.         {
  56.                 res += nums[i];
  57.         }
  58.         printf("三角形顶端走到底端的最大和为 %d\n", res);

  59.         system("pause");
  60. }
复制代码

输出结果:
75
                                        95    64
                                     17    47    82
                                  18    35    87    10
                               20     4    82    47    65
                            19     1    23    75     3    34
                         88     2    77    73     7    63    67
                      99    65     4    28     6    16    70    92
                   41    41    26    56    83    40    80    70    33
                41    48    72    33    47    32    37    16    94    29
             53    71    44    65    25    43    91    52    97    51    14
          70    11    33    28    77    73    17    78    39    68    17    57
       91    71    52    38    17    14    91    43    58    50    27    29    48
    63    66     4    68    89    53    67    30    73    16    69    87    40    31
  4    62    98    27    23     9    70    98    73    93    38    53    60     4    23
产生的序列是
  75  95  47  87  82  75  73  28  83  47  43  73  91  67  98
三角形顶端走到底端的最大和为 1064
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-6-30 17:59:28 | 显示全部楼层
数据小随从 发表于 2020-6-30 17:23
我不知道错在哪里,为什么大家的答案都是1074,我算的是1064
#include
#include

用 <> 发代码!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-7-1 21:08:11 | 显示全部楼层

谢谢,我以前一直不知道他们这个怎么发的,我以为要特殊的软件编辑
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-2-6 12:38:28 | 显示全部楼层
  1. #include <iostream>
  2. using namespace std;
  3. #define max(x,y) ((x)>(y)?(x):(y))
  4. int Array[]={
  5. 75,
  6. 95,64,
  7. 17,47,82,
  8. 18,35,87,10,
  9. 20,04,82,47,65,
  10. 19,01,23,75,03,34,
  11. 88,02,77,73,07,63,67,
  12. 99,65,04,28,06,16,70,92,
  13. 41,41,26,56,83,40,80,70,33,
  14. 41,48,72,33,47,32,37,16,94,29,
  15. 53,71,44,65,25,43,91,52,97,51,14,
  16. 70,11,33,28,77,73,17,78,39,68,17,57,
  17. 91,71,52,38,17,14,91,43,58,50,27,29,48,
  18. 63,66,04,68,89,53,67,30,73,16,69,87,40,31,
  19. 04,62,98,27,23, 9,70,98,73,93,38,53,60,04,23
  20. };
  21. #define width 15
  22. void setmax(int i,int j)
  23. {
  24.     if(j == 0)
  25.         Array[i*(i+1)/2+j] += Array[i*(i-1)/2+j];
  26.     else if(j == i)
  27.         Array[i*(i+1)/2+j] += Array[i*(i-1)/2+j-1];
  28.     else
  29.     Array[i*(i+1)/2+j] += max(Array[i*(i-1)/2+j],Array[i*(i-1)/2+j-1]);
  30. }
  31. int main()
  32. {
  33.     for(int i=1;i<width;i++)
  34.         for(int j=0;j<=i;j++)
  35.             setmax(i,j);
  36.     int maxum = 0;
  37.     for(int i=width*(width-1)/2+0;i<width*(width-1)/2+15;i++)
  38.         if(maxum<Array[i])
  39.             maxum = Array[i];
  40.     cout << maxum;
  41. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 19:48

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表