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)


相关推荐

  • Linux中磁盘数据被误删,怎么恢复

    如果你要是对linux分区和挂载不理解,建议看下:https://blog.csdn.net/qq_41276657/article/details/105168312eg:假如文件被不小心删除操作:1,先卸载磁盘,防止数据被新添加数据替换2,下载extundelete恢复工具https://pan.baidu.com/s/1ocBNA5KTgmVEeFa30-fkSQ3,如果用ex…

  • Laravel 引入自定义类库或第三方类库

    Laravel 引入自定义类库或第三方类库

    2021年10月25日
  • ireport教程_linear predictor

    ireport教程_linear predictor三元元算($F{username}.equals(“a”))?”它是a”:”它不是a”

  • Perl正则表达式(2) – 用正则表达式进行匹配

    Perl正则表达式(2) – 用正则表达式进行匹配Perl正则表达式2.用正则表达式进行匹配2.1用m//进行匹配到目前为止,我们都是讲正则表达式的内容写在一对斜线内,如/fred/。但其实这是m//的简写,其中m代表match,和之前看到的qw//类似,我么可以自行选择用于保卫内容的一堆字符作为边界,所以上面这个例子可以改写为m{fred},m[fred],m!fred!等。在不冲突的情况下,建议使用双斜线//或…

  • 框架介绍

    MVC模式MVC模式介绍Django中的MVC模式分为三个部分此外,Django还有一个URL分发器。它的作用是将一个个URL的页面请求分别发给不同的Views处理,Views再调用相应的Mod

  • SCI论文投稿Cover Letter的写作

    SCI论文投稿Cover Letter的写作http://www.dxy.cn/bbs/topic/19651815SCI论文投稿CoverLetter的写作和中文投稿有很大的不同,CoverLetter的撰写对于新手而言不知该写什么,而对于老手往往又被忽视,CoverLetter重要吗?可有可无吗?下面我将从科学网转载系列有关CoverLetter的帖子,但愿对于新手、老手都有所帮助:#1CoverLet

发表回复

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

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