回复 @Satoshi
头像不错

回复 @000000 :
hhjhhhhh

这是一道简单的动态规划题，定义两个一样的数组，塔储存两遍，主要的地方也就两点：
从后到前利用动规得到整个的最大值，这是主体部分。

 for ( int i = n-1; i >= 1; --i )

 for ( int j = 1; j <= i; ++j )

 if ( num[i+1][j] > num[i+1][j+1] )

 num[i][j] += num[i+1][j];

 else num[i][j] += num[i+1][j+1];

然后再根据动规留下的痕迹从前往后输出路径。

 cout << ans[1][1] << " ";

 for ( int i = 2; i != n+1; ++i ) {

 for ( int j = 1; j != i+1; ++j ) {

 if ( k - num[i][j] == p ) {

 cout << ans[i][j] << " ";

 k = num[i][j];

 p = ans[i][j];

 break;

 }

 }

 }

也许还有更简单的方法，我就知道这么多了。。

最反感的就是path数组了。

输出路径搞了将近一节课............

输出路径时，设第一个点是ans（由下及上用动归，ans=f[1,1]),输出对应a[1,1]，ans=ans-a[i,j]每一行搜索一次输出对应a[i,j]第九个点过不了ans有重复

program shuta;
var
i,j,n,max,temp:longint;
a,f:array[0..1000,0..1000] of longint;
path:array[0..1000] of longint;
begin
assign(input,'shuta.in');
assign(output,'shuta.out');
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do
for j:=1 to i do
read(a[i,j]);
f[1,1]:=a[1,1];
for i:=2 to n do
for j:=1 to i do
begin
f[i,j]:=f[i-1,j];
if f[i-1,j]<f[i-1,j-1] then
f[i,j]:=f[i-1,j-1];
f[i,j]:=f[i,j]+a[i,j];
if f[i,j]>max then
begin
max:=f[i,j];
path[n]:=a[i,j];
temp:=j;
end;
end;
for i:=n-1 downto 1 do
begin
if f[i,temp]>f[i,temp-1] then
path[i]:=a[i,temp]
else
begin
path[i]:=a[i,temp-1];
dec(temp);
end;
end;
writeln(max);
for i:=1 to n-1 do
write(path[i],' ');
writeln(path[n]);
close(input);
close(output);
end.

根部偏左？？和路径偏左有啥区别？

一开始理解错题意了。。。。注意根部偏左- -。。。我还以为整个路径偏左~ 又自行脑补了

用长整QwQ

加一个Path数组

谁能告诉我~ 什么叫动态规划？