TOJ 4674 数塔II DP-蒲公英云

TOJ 4674 数塔II DP

心已赠人 2022-05-18 10:59 281阅读 0赞

4674: 数塔II

描述

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少，并输出一条路径。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输入

输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。

输出

对于每个测试实例，每行先输出可能得到的最大和，后面输出从第一层到最后一层所选数字的编号（即第几列的数）。

格式见样例。

样例输入

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

样例输出

30: 1 1 1 2 2

提示

从第一层到各层的数字分别为：
第1层第1列：7
第2层第1列：3
第3层第1列：8
第4层第2列：7
第5层第2列：5

倒着做上去，用一个b数组记录一下初始值，再正着下来找值相等的。

#include<stdio.h>
int main()
{
    int a[99][99],b[99][99];
    int t,n,i,j,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);        
        for(i=0;i<n;i++)
        {
            for(j=0;j<=i;j++)
            {
                scanf("%d",&a[i][j]);
                b[i][j]=a[i][j];
            }
        }         
        for(i=n-1;i>0;i--)
        {
            for(j=0;j<i;j++)
            {
                if(a[i][j]>=a[i][j+1])
                a[i-1][j]=a[i][j]+a[i-1][j];
                else
                a[i-1][j]=a[i][j+1]+a[i-1][j];
            }            
        }
        printf("%d:",a[0][0]);
        k=0;
        for(i=0;i<n;i++)
        {
            printf(" %d",k+1);
            for(j=0;j<=i+1;j++)
            {
                if(a[i][k]==a[i+1][j]+b[i][k]&&(j==k||j-1==k))
                {
                    k=j;
                    break;
                }
            }
        }
        printf("\n");
    }
    return 0;
}