HDU——1176 免费馅饼(动态规划 类似数塔问题)

2023-12-28 14:32

本文主要是介绍HDU——1176 免费馅饼(动态规划 类似数塔问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Problem Description

都说天上不会掉馅饼,但有一天gameboy正走在回家的小径上,忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了,这馅饼别处都不掉,就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了,所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人,所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏,虽然在游戏中是个身手敏捷的高手,但在现实中运动神经特别迟钝,每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标:
这里写图片描述

为了使问题简化,假设在接下来的一段时间里,馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置,因此在第一秒,他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼?(假设他的背包可以容纳无穷多个馅饼)

Input

输入数据有多组。每组数据的第一行为以正整数n(0

Output

每一组输入数据对应一行输出。输出一个整数m,表示gameboy最多可能接到m个馅饼。
提示:本题的输入数据量比较大,建议用scanf读入,用cin可能会超时。

Sample Input

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

Sample Output

4

解题思路:

典型的动态规划,与数塔问题(详解)十分相似。数塔问题的解决是依靠二维矩阵tower[][]来解决的,从顶端点出发,每一个节点可以选择向下一层的左或者右走,一直走到最底层,找出一条路径,使得路径上的数字之和最大.假设当前在tower[i][j](第i层的第j个位置),那么下一次可到达的节点为tower[i+1][j]或者tower[i+1][j+1].
将本题转化为数塔问题解决,那么本题中时间就是数塔pie的层数t,每一层有11个节点(0 ~ 10),例如:pie[t][i]表示gameboy第t秒的时候,处于节点i处。注:本题中在从上一层向下一层跳时,可以向左,向右,也可以就在原地,所以每一次跳时都有三个选择(注意左右边界)。

代码:

#include <stdio.h>
#include <string.h>
using namespace std;int pie[100001][11] = {0};int maxvalue(int a ,int b ,int c){  int temp = a;if(b > temp)temp = b;if(c > temp)temp = c;return temp;
}
int main(){int n , t , x ,i , j , maxt = 0;while(scanf("%d",&n) != EOF){memset(pie , 0 , sizeof(pie));if(n == 0)break;for(i = 0 ; i < n ; i ++){scanf("%d %d",&x ,&t);if( t > maxt)maxt = t;pie[t][x] += 1;}for( i = maxt - 1 ; i >= 0 ; i --){   //选择下一跳的方向pie[i][0] = pie[i][0] + pie[i+1][0] > pie[i][0] + pie[i+1][1] ? pie[i][0] + pie[i+1][0] : pie[i][0] + pie[i+1][1];for(j = 1 ; j <= 9 ; j ++){pie[i][j] = maxvalue(pie[i][j] + pie[i+1][j-1] , pie[i][j] + pie[i+1][j] ,pie[i][j] + pie[i+1][j+1]);}pie[i][10] = pie[i][10] + pie[i+1][10] > pie[i][10] + pie[i+1][9] ? pie[i][10] + pie[i+1][10] : pie[i][10] + pie[i+1][9];}printf("%d\n",pie[0][5]);}return 0;
}

这篇关于HDU——1176 免费馅饼(动态规划 类似数塔问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/546270

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :