加载中...

POJ 3176 - Cow Bowling


问题描述

输入一个n层的三角形,第i层有i个数,求从第1层到第n层的所有路线中,权值之和最大的路线。

规定:第i层的某个数只能连线走到第i+1层中与它位置相邻的两个数中的一个。

提示

用二维数组 way[][] 靠左存储三角形内的数据,那么连线规则变更为

way[i][j] → Way[i+1][j]

Way[i][j] → Way[i+1][j+1]

注意way[][] 初始化为输入时的三角形数值,此时 way[i][j] 表示该点位置上的权值,没输入的位置初始化为0。

解题思路

动态规划

way[i][j] 表示以第i行j列的位置作为终点的路线的最大权值。 (注意区分初始化时的意义)

那么 way[i][j] 的最大值取决于 way[i-1][j-1]way[i-1][j],从这两者之间筛选出最大值,加到 way[i][j] 上,即为 way[i][j] 的最大权值。

最后只要比较第n行中所有位置的权值 way[n][j] ,最大的一个即为所求。

顺带一提,[POJ1163](.//这个大小是根据本题而决定的一个小优化,不同的题具体申请大小

这两次操作相当于先申请了二维数组way的行数,再逐行申请列数,这就相当于间接申请了一个二维数组,而且每行的列数还可以不同,优化了空间使用率。

AC 源码

//Memory Time 
//468K   172MS 

#include<iostream>
using namespace std;

int max(int a,int b)
{
    return a>b?a:b;
}

int main(int i,int j)
{
    int n;
    while(cin>>n)
    {
        int **way=new int*[n+1];   //动态申请二维数组的第一维,每个元素都是一个一维数组的指针

        /*Input & Initial*/

        for(i=0;i<=n;i++)
        {
            way[i]=new int[i+2]; //动态申请二维数组的第二维,每一行的空间
            for(j=0;j<=i+1;j++)
                way[i][j]=0;   //不能用memset初始化

            if(i!=0)
                for(j=1;j<=i;j++)
                    cin>>way[i][j];
        }

        /*Dp*/

        int max_weight=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=i;j++)
            {
                way[i][j] += max(way[i-1][j-1],way[i-1][j]);

                if(i==n && max_weight<way[i][j])
                    max_weight=way[i][j];
            }

        cout<<max_weight<<endl;

        delete[] way;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
  目录