Cow Bowling(动态规划)
发布日期:2021-10-16 05:05:09
浏览次数:8
分类:技术文章
本文共 1647 字,大约阅读时间需要 5 分钟。
Cow Bowling
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 19855 | Accepted: 13164 |
Description
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:
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.
Input
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 5
Sample Output
30
Hint
Explanation of the sample:
7 * 3 8 * 8 1 0 * 2 7 4 4 * 4 5 2 6 5The highest score is achievable by traversing the cows as shown above.
Source
题意:
求一条路径,使从头到尾和最大。
思路:
简单动态规划。
代码:
#include#include #include using namespace std;int num[550][550],f[550][550];int sum;int main(){ int i,j; int n; cin>>n; for(i=1;i<=n;i++) { for(j=1;j<=i;j++) cin>>num[i][j]; } for(j=1;j<=n;j++)f[n][j]=num[n][j]; for(i=n-1;i>=1;i--) { for(j=1;j<=i;j++) f[i][j]=num[i][j]+max(f[i+1][j],f[i+1][j+1]); } cout< <
转载地址:https://blog.csdn.net/sinat_37668729/article/details/77070883 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年03月26日 18时25分07秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Bootstrap基础10(标签页)
2019-04-21
Vue系列之 => 自定义全局指定让文本框自动获取焦点
2019-04-21
前端学习之路-CSS介绍,Html介绍,JavaScript介绍
2019-04-21
PHP全栈从入门到精通1
2019-04-21
第四周总结
2019-04-21
Linux安装jdk
2019-04-21
【转】MATLAB在一幅图上添加多个纵坐标轴
2019-04-21
linux c编程操作数据库(sqlite3应用)
2019-04-21
jQuery中.live()方法的使用方法
2019-04-21
核心技术篇:1.移动应用的根源---网络
2019-04-21
Codis集群的搭建与使用
2019-04-21
如何在Linux环境下编译lib 库
2019-04-21
KVC 字典转模型构造函数
2019-04-21
ios 线程笔记(一)
2019-04-21
C#二进制与字符串之间的相互转换
2019-04-21
大数据JAVA基础第三天
2019-04-21
使用匿名内部类调用start方法
2019-04-21
小游戏之买房记
2019-04-21
is 和==的区别
2019-04-21