POJ_3176_Cow_Bowling(数字三角形)

描述


http://poj.org/problem?id=3176

给出一个三角形,每个点可以走到它下面两个点,将所有经过的点的值加起来,问最大的和是多少.

分析

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using std :: max;
 5
 6 const int maxn=355;
 7 int a[maxn][maxn],f[maxn][maxn];
 8 int n;
 9
10 int dfs(int i,int j)
11 {
12     if(f[i][j]!=-1) return f[i][j];
13     if(i==n) return f[i][j]=a[i][j];
14     return f[i][j]=a[i][j]+max(dfs(i+1,j),dfs(i+1,j+1));
15 }
16
17 void init()
18 {
19     scanf("%d",&n);
20     for(int i=1;i<=n;i++)
21     {
22         for(int j=1;j<=i;j++)
23         {
24             scanf("%d",&a[i][j]);
25         }
26     }
27     memset(f,-1,sizeof(f));
28 }
29
30 int main()
31 {
32 #ifndef ONLINE_JUDGE
33     freopen("cow.in","r",stdin);
34     freopen("cow.out","w",stdout);
35 #endif
36     init();
37     printf("%d\n",dfs(1,1));
38 #ifndef ONLINE_JUDGE
39     fclose(stdin);
40     fclose(stdout);
41 #endif
42     return 0;
43 }

记忆化搜索

 1 #include<cstdio>
 2 #include<algorithm>
 3 using std :: max;
 4
 5 const int maxn=355;
 6 int n;
 7 int a[maxn][maxn],f[maxn][maxn];
 8
 9 void solve()
10 {
11     for(int i=n-1;i>=1;i--)
12     {
13         for(int j=1;j<=i;j++)
14         {
15             f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
16         }
17     }
18     printf("%d\n",f[1][1]);
19 }
20
21 void init()
22 {
23     scanf("%d",&n);
24     for(int i=1;i<=n;i++)
25     {
26         for(int j=1;j<=i;j++)
27         {
28             scanf("%d",&a[i][j]);
29         }
30     }
31     for(int j=1;j<=n;j++) f[n][j]=a[n][j];
32 }
33
34 int main()
35 {
36 #ifndef ONLINE_JUDGE
37     freopen("cow.in","r",stdin);
38     freopen("cow.out","w",stdout);
39 #endif
40     init();
41     solve();
42 #ifndef ONLINE_JUDGE
43     fclose(stdin);
44     fclose(stdout);
45 #endif
46     return 0;
47 }

动态规划



POJ_3176_Cow_Bowling(数字三角形)

时间: 04-21

POJ_3176_Cow_Bowling(数字三角形)的相关文章

数字三角形

数字三角形必须经过某一个点,使之走的路程和最大 输入格式: 第1行n,表示n行 (n<=25), 第2到n+1行为每个的权值,第n+2行为两个数x,y表示必须经过的点 输出格式: 输出最大值 样例1 输入: 2 1 1 1 1 1 输出: 2 //11 月 23 日 2015 #include <stdio.h> int num[26][26];//存储数字三角形的权值 int route[26][2];//记录临时最优路径 int n; int s1,s2;//以特殊点分为上半段和下半

蓝桥杯 算法训练 ALGO-124 数字三角形

算法训练 数字三角形 时间限制:1.0s   内存限制:256.0MB 问题描述 (图3.1-1)示出了一个数字三角形. 请编一个程序计算从顶至底的某处的一条路 径,使该路径所经过的数字的总和最大. ●每一步可沿左斜线向下或右斜线向下走: ●1<三角形行数≤100: ●三角形中的数字为整数0,1,-99: . (图3.1-1) 输入格式 文件中首先读到的是三角形的行数. 接下来描述整个三角形 输出格式 最大总和(整数) 样例输入 573 88 1 02 7 4 44 5 2 6 5 样例输出 3

4829 [DP]数字三角形升级版

4829 [DP]数字三角形升级版 时间限制: 1 s 空间限制: 16000 KB 题目等级 : 黄金 Gold 题解 题目描述 Description 从数字三角形的顶部(如图,第一行的5表示行数)到底部有很多条不同的路径.对于每条路径,把路径上面的数加起来可以得到一个和,且!!!!!!!!! ================================================================================== =================

各种数字三角形

数字三角形 经典例题,有记忆化搜索,正推,逆推三种方法 如果记录路径,可以开一个数组记录状态是由哪个子状态推出来的 #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> using namespace std; const int maxn = 200; int n,dp[maxn][maxn],value[maxn][

【递归】数字三角形 简单dp

[递归]数字三角形 题目描述 对于大多数人来说,“我们是这么的正常,因此也就这么的平庸.”而天才总是与众不同的,所以当邪狼问修罗王:“老大,你蹲在那儿一动不动看了有半个小时了,蚂蚁有那么好看吗?” 修罗王是这样回答的:“我在思索人生的意义,你看这蚂蚁的面前有无数的道路选择,但它不知道选择哪条路可以到达目标,也不知道哪条路上有更多的食物,更不知道现在选择的道路对它以后的影响……” 如图所示,有一个层数为n(n≤1000)的数字三角形.现有一只蚂蚁从顶层开始向下走,每走下一级时,可向左下方向或右下方

hihoCoder 1037 数字三角形 最详细的解题报告

题目来源:hihoCoder 1037 数字三角形 解题思路:请好好看看 提示一.提示二.提示三 具体算法(java版,可以直接AC) import java.util.Scanner; public class Main { public static int[][] rewards; public static int[][] best; public static void main(String[] args) { Scanner scanner = new Scanner(System

#1037 : 数字三角形

#1037 : 数字三角形 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 问题描写叙述 小Hi和小Ho在经历了螃蟹先生的任务之后被奖励了一次出国旅游的机会,于是他们来到了大洋彼岸的美国. 美国人民的生活很有意思,常常会有形形色色.奇奇怪怪的活动举办,这不.小Hi和小Ho刚刚下飞机,就赶上了当地的迷宫节活动.迷宫节里展览出来的迷宫都特别的有意思,可是小Ho却相中了一个事实上并不怎么像迷宫的迷宫--由于这个迷宫的奖励很丰富~ 于是小Ho找到了小Hi,让小Hi帮助他获取尽可能

数字三角形2

题目描述 数字三角形 要求走到最后mod  100最大 输入 第1行n,表示n行  < =25 第2到n+1行为每个的权值 输出 mod  100最大值 样例输入 2 1 99 98 样例输出 99 #include <bits/stdc++.h> #include <iostream> #include <cstdio> #include <ctime> #include <cstring> using namespace std; ty

#1037 : 数字三角形(基础DP)

题目链接 #1037 : 数字三角形 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 问题描述 小Hi和小Ho在经历了螃蟹先生的任务之后被奖励了一次出国旅游的机会,于是他们来到了大洋彼岸的美国.美国人民的生活非常有意思,经常会有形形色色.奇奇怪怪的活动举办,这不,小Hi和小Ho刚刚下飞机,就赶上了当地的迷宫节活动.迷宫节里展览出来的迷宫都特别的有意思,但是小Ho却相中了一个其实并不怎么像迷宫的迷宫--因为这个迷宫的奖励非常丰富~ 于是小Ho找到了小Hi,让小Hi帮助他获取

数字三角形问题

1.数字三角形问题1: •    7 •   3 8 •  8 1 0 • 2 7 4 4 •4 5 2 6 5 •从第一层走到最后一层,每次向左下或右下走,求路径的最大权值和. 思路: •如果利用转移方程求解原问题? •f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j] •1.从上向下转移,即i从小到大? •2.从下向上转移,即i从大到小? •观察转移方程的性质 •因为第i行的解要由第i+1行的解得到,所以必须从下向上转移!! 代码: 1 #include <