• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ3176 – Cow Bowling

    ACM-POJ EXP 136阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    输入一个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 和这题是双子题,两道题基本一模一样,区别仅仅在于n的取值范围。所以说如果是用动态申请二维数组的同学,就可以直接把代码复制到POJ1163提交AC了。


    顺便说一下动态申请二维数组的方法

    C++的new函数是无法直接申请二维空间的,但是可以间接申请。

    以我的程序为例,先申请一个“指向一维指针数组”的二维指针

    int **way=new int*[n+1];

    这个数组way[]的每一个元素都是一个指针

    再利用for循环,逐行申请空间,使每一个元素(指针)指向一个“一维数组”

    Way[i]=new int[i+2]; //这个大小是根据本题而决定的一个小优化,不同的题具体申请大小

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


    转载请注明:EXP 技术分享博客 » POJ3176 – Cow Bowling

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址