3

POJ 3176 - Cow Bowling

 2 years ago
source link: https://exp-blog.com/algorithm/poj/poj3176-cow-bowling/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
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的行数，再逐行申请列数，这就相当于间接申请了一个二维数组，而且每行的列数还可以不同，优化了空间使用率。

//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;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK