数字三角 [SCU – 1114]

数字三角 [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[]合到数字的正负上:数字的绝对值表示数字大小,正负号表示此路是否被选中,可以省去部分内存空间。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注