- 科技
- DP数塔
#include<bits/stdc++.h>
using namespace std
;
int main()
{
int C
,N
;
cin
>>C
;
while(C
--)
{
cin
>>N
;
int a
[N
+1][N
+1],dp
[N
+1][N
+1];
memset(a
,0,sizeof(a
));
memset(dp
,0,sizeof(dp
));
for(int i
=1;i
<=N
;i
++)
{
for(int j
=1;j
<=i
;j
++)
{
cin
>>a
[i
][j
];
}
}
for(int i
=1;i
<=N
;i
++)
{
dp
[N
][i
]=a
[N
][i
];
}
for(int i
=N
;i
>=2;i
--)
{
for(int j
=1;j
<=i
;j
++)
{
dp
[i
-1][j
]=a
[i
-1][j
]+max(dp
[i
][j
],dp
[i
][j
+1]);
}
}
cout
<<dp
[1][1]<<endl
;
}
}
Processed:
0.200, SQL:
8
