数字三角 [SCU – 1114]
简单的动态规划，但是此题需要把路径记下来，
动态规划得从几近成功开始考虑，比如只有2的情形，只需要选两侧更大的那个即可。3层的时候就假设第2层已经知道最大收益，那就选走了第2层以及加上走第2层的收益最大的那个。每次走把当前选的是左还是右记下来，当走到最上层的时候，再反着去读走的那条路径即可。
#include <cstdio>
int main(void)
{
int **acc,**moto;
char **turnRight;
int i,j,N;
scanf("%d",&N);
turnRight = new char* [N];
acc = new int* [N];
moto = new int* [N];
for( i=0;i<N;i++)
{
turnRight[i]=new char [i+1];
acc[i]=new int [i+1];
moto[i]=new int [i+1];
for(j=0;j<i+1;j++)
{
scanf("%d",&moto[i][j]);
acc[i][j]=moto[i][j];
turnRight[i][j]=0;
}
}
for(i=N-2;i>=0;i--)
{
for(j=0;j<i+1;j++)
{
if(acc[i+1][j]<acc[i+1][j+1])
{
acc[i][j]+=acc[i+1][j+1];
turnRight[i][j]=1;
}
else
{
acc[i][j]+=acc[i+1][j];
}
}
}
#ifdef MALICVERBOSE
for(i=0;i<N;i++)
{
for(j=0;j<i+1;j++)
{
printf("%d\t",moto[i][j]);
}
printf("\n");
}
#endif
printf("%d\n",acc[0][0]);
j=0;
for(i=0;i<N;i++)
{
if(i>0)
printf(" ");
printf("%d",moto[i][j]);
if(turnRight[i][j]==1)
j+=1;
}
printf("\n");
for(i=0;i<N;i++)
{
delete [] turnRight[i];
delete [] acc[i];
}
delete [] turnRight;
delete [] acc;
return 0;
}
应该还有一个省空间的方法，对于此题，所有的数据都是正的，我们可以把turnRight[]合到数字的正负上：数字的绝对值表示数字大小，正负号表示此路是否被选中，可以省去部分内存空间。