当前位置: 首页 > >

nefuoj 17 数字三角形

发布时间:

数字三角形






Problem:17


Time Limit:1000ms


Memory Limit:65536K






Description



7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。
注意:路径上的每一步只能从一个数走到下一层上和它最*的左边的那个数或者右边的那个数。





Input



输入数据有多组,每组输入的是一行是一个整数N (1 < N <= 100),给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。





Output



输出最大的和。





Sample Input



5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
3
1
2 3
1 1 1





Sample Output



30
5





Hint



dp





#include
#include
using namespace std;

int main()
{
int n;
int data[101][101],inp[101][101];
while(cin>>n)
{
memset(data,0,sizeof(data));
memset(inp,0,sizeof(inp));
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
cin>>data[i][j];
if(i==1)
inp[i][j]=data[i][j];
else
inp[i][j]=max(inp[i-1][j],inp[i-1][j-1])+data[i][j];
}
int tmp=0;
for(int k=1;k<=n;k++)
if(tmp tmp=inp[n][k];
cout < }
return 0;
}




友情链接: