POJ3176 Cow Bowling
发布日期:2022-02-25 01:17:47
浏览次数:44
分类:技术文章
本文共 1517 字,大约阅读时间需要 5 分钟。
The cows don't use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a standard bowling-pin-like triangle like this:
Input 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5Then the other cows traverse the triangle starting from its tip and moving "down" to one of the two diagonally adjacent cows until the "bottom" row is reached. The cow's score is the sum of the numbers of the cows visited along the way. The cow with the highest score wins that frame. Given a triangle with N (1 <= N <= 350) rows, determine the highest possible sum achievable.
Line 1: A single integer, N Lines 2..N+1: Line i+1 contains i space-separated integers that represent row i of the triangle.
Output Line 1: The largest sum achievable using the traversal rules
Sample Input 573 88 1 02 7 4 44 5 2 6 5Sample Output
30Hint
Explanation of the sample:
7 * 3 8 * 8 1 0 * 2 7 4 4 * 4 5 2 6 5
The highest score is achievable by traversing the cows as shown above.
解题思路
动态规划的入门级题目,一道数塔题目,题目分析时可以自顶向下,但解题时自底向上的效果会更好,这题的转移方程为a[i][j] += max(a[i + 1][j],a[i + 1][j + 1]);
#include#include using namespace std;int a[10005][10005];int main(){ int n; while(cin>>n){ for(int i = 1;i <= n;i++){ for(int j = 1;j <= i;j++){ cin>>a[i][j]; } } for(int i = n - 1;i >= 1;i--){ for(int j = 1; j <= i;j++){ a[i][j] += max(a[i + 1][j],a[i + 1][j + 1]); } } cout< <
转载地址:https://blog.csdn.net/qq_37755550/article/details/80470684 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月24日 03时38分29秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Linux下文件如果没有权限不能被Apache访问
2019-04-27
Linux内核学习四库全书
2019-04-27
Linux内核模块编程入门
2019-04-27
使用Cacti监控你的网络Cacti的安装
2019-04-27
2011年6月编程语言关注度排行
2019-04-27
Varnish使用小结
2019-04-27
千万级并发HAproxy均衡负载系统介绍
2019-04-27
什么是A记录、MX记录、CNAME记录
2019-04-27
MongoDB简介
2019-04-27
Varnish purges 缓存清除
2019-04-27
Linux下redis安装部署
2019-04-27
水平切分与垂直切分
2019-04-27
MySQL引擎
2019-04-27
MySQL下的NoSQL解决方案HandlerSocket
2019-04-27
Apache服务器下使用 ab 命令进行压力测试
2019-04-27
查看Firefox中的缓存
2019-04-27
http header头设置反向代理不缓存
2019-04-27
配置MySQL主从复制
2019-04-27
CI框架如何删除地址栏的 index.php
2019-04-27
expires与etag控制页面缓存的优先级
2019-04-27