POJ 3176-Cow Bowling(DP||记忆化搜索)

POJ 3176-Cow Bowling(DP||记忆化搜索)

Cow Bowling
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 14210   Accepted: 9432

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   5

Then 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

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Sample Output

30
数字三角形问题。。能够自底向上坐dp dp[i][j]=ma[i][j]+max(dp[i+1][j],dp[i+1][j+1])
巨水 。。想当初半年前自己懵懵懂懂的刷dp啥都不懂。。哎  真是个悲伤的故事。。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define ll long long
#define maxn 360
#define pp pair<int,int>
#define INF 0x3f3f3f3f
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
int n,dp[maxn][maxn],ma[maxn][maxn];
void solve()
{
	for(int i=0;i<n;i++)
		dp[n-1][i]=ma[n-1][i];
	for(int i=n-2;i>=0;i--)
		for(int j=0;j<=i;j++)
			dp[i][j]=max(ma[i][j]+dp[i+1][j],ma[i][j]+dp[i+1][j+1]);
	printf("%d\n",dp[0][0]);
}
int main()
{
	while(~scanf("%d",&n))
	{
		for(int i=0;i<n;i++)
			for(int j=0;j<=i;j++)
			scanf("%d",&ma[i][j]);
		memset(dp,0,sizeof(dp));
		solve();
	}
	return 0;
}

也能够自顶向下记忆化搜索。。然后状态数组含义都差点儿相同 。。个人觉着搜索比較好写。。。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define ll long long
#define maxn 360
#define pp pair<int,int>
#define INF 0x3f3f3f3f
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
int n,dp[maxn][maxn],ma[maxn][maxn];
int dfs(int x,int y)
{
	if(x==n-1)return ma[x][y];
	if(dp[x][y]>=0)return dp[x][y];
	dp[x][y]=0;
	dp[x][y]+=(ma[x][y]+max(dfs(x+1,y),dfs(x+1,y+1)));
	return dp[x][y];
}
int main()
{
	while(~scanf("%d",&n))
	{
		for(int i=0;i<n;i++)
			for(int j=0;j<=i;j++)
			scanf("%d",&ma[i][j]);
		memset(dp,-1,sizeof(dp));
		printf("%d\n",dfs(0,0));
	}
	return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/109498.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • eplan激活码破解步骤【2021最新】

    (eplan激活码破解步骤)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

  • pycahrm 激活码_在线激活

    (pycahrm 激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlCJM5ZJBPHS-eyJsaWNlbnNlSWQi…

  • 影视短视频剪辑的完整操作流程(普通人也能学会)

    影视短视频剪辑的完整操作流程(普通人也能学会)嗨喽,大家好,我是会玩运营,能写代码,文案设计样样精通的江湖美男子菜鸟哥,一名走在营销路上的小菜鸟。点击上方蓝字“关注”,每天为你分享有用的营销运营干货。上一篇文章我们讲解了《全网最全抖音运营攻略》,相信看完这篇文章的朋友对于短视频运营多少有了一定的了解,文中的2020年抖音用户画像报告,我们了解到短视频用户对于影视类的作品关注度还是非常高的,今天我们就结合案例来为大家进行更加详细的讲解。本文将带你初步了解抖音、快手短视频中影视剪辑的完整操作流程,没有过多复杂的骚操作,零基础的普通人也能够看懂。

  • 背包问题九讲笔记_01背包[通俗易懂]

    背包问题九讲笔记_01背包[通俗易懂]摘自TianyiCui童鞋的《背包问题九讲》,稍作修改,方便理解。01背包问题描述已知:有一个容量为V的背包和N件物品,第i件物品的重量是weight[i],收益是cost[i]。限制:每种物品只有一件,可以选择放或者不放问题:在不超过背包容量的情况下,最多能获得多少价值或收益相似问题:在恰好装满背包的情况下,最多能获得多少价值或收益这里,我们先讨论在不超过背包容量的情况

  • 制作QQ微信支付宝三合一收款码

    制作QQ微信支付宝三合一收款码

  • moxa串口服务器型号,moxa串口服务器产品配置说明

    moxa串口服务器产品配置说明内容精选换一换为弹性云服务器配置的安全组规则未生效。以下排查思路根据原因的出现概率进行排序,建议您从高频率原因往低频率原因排查,从而帮助您快速找到问题的原因。如果解决完某个可能原因仍未解决问题,请继续排查其他可能原因。当安全组规则配置有误时,无法按照规划的安全组规则对云服务器进行保护。您可以按照以下几点原因对安全组配置进行检查:安全组规则方向设置错误,使用坐席工号(…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号