热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HDU1176:免费馅饼问题的动态规划解法分析

题目“免费馅饼”通过动态规划方法进行了解析。该问题的时间限制为Java2000ms和其他语言1000ms,内存限制为Java65536K和其他语言32768K。本文详细探讨了如何利用动态规划算法高效求解此问题,并对算法的时间复杂度和空间复杂度进行了深入分析。此外,还提供了具体的实现步骤和代码示例,帮助读者更好地理解和应用这一方法。


免费馅饼
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 23808    Accepted Submission(s): 8025





Problem Description


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

为了使问题简化,假设在接下来的一段时间里,馅饼都掉落在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



 




Author


lwg


 




Recommend


We have carefully selected several similar problems for you:  2084 1069 1058 1257 1421 


 




Statistic | Submit | Discuss | Note

今天做了一道有趣的dp题。。。题目不难。。但是居然坑了我。。

题解:dp[i][j]代表在第j秒时在第i个位置最多可以得到多少个馅饼。。

f[i][j] 代表第j秒时在第i个位置有多少个馅饼掉下。。

dp[i][j] = max(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1])+f[i][j];

本来状态方程式没错的。但是忽略了一种情况。。比如dp[0][1]这是不可能存在的。。因为第一秒时是不可能到达

0这个点的。。坑!

所以还要判断一下这个状态是不是可以到达的。。

最后 代码:

#include
#include
#include
#include
#include
using namespace std;
int dp[11][100002];
int f[11][100002];
int main() {
int n,i,j;
int l,r;
while(scanf("%d",&n) && n!=0) {
memset(f,0,sizeof(f));
int Max = 0;
for(i=0;i scanf("%d%d",&l,&r);
f[l][r]++;
Max = Max }
memset(dp,0,sizeof(dp));
int sum = 0;
//dp[5][0] = 1;
for(i=1;i<=Max;i++) {
for(j=0;j<11;j++) {
sum = dp[j][i-1];
if(abs(j-5)<=i && j>0) sum = max(dp[j-1][i-1],sum);
if(abs(j-5)<=i && j<10) sum = max(dp[j+1][i-1],sum);
if(abs(j-5)<=i)sum+=f[j][i];
dp[j][i] = max(sum,dp[j][i]);
}
}
sum = 0;
for(i=0;i<11;i++) {
sum = max(dp[i][Max],sum);
}
printf("%d\n",sum);
}
return 0;
}



hdu1176免费馅饼(dp),布布扣,bubuko.com


推荐阅读
  • 在HDU 1166敌军布阵问题中,通过运用线段树数据结构,可以高效地计算指定区间的敌军数量。该算法不仅能够在限定的时间和内存条件下快速求解,还能够灵活应对动态变化的战场局势,为实时决策提供支持。 ... [详细]
  • 在处理遗留数据库的映射时,反向工程是一个重要的初始步骤。由于实体模式已经在数据库系统中存在,Hibernate 提供了自动化工具来简化这一过程,帮助开发人员快速生成持久化类和映射文件。通过反向工程,可以显著提高开发效率并减少手动配置的错误。此外,该工具还支持对现有数据库结构进行分析,自动生成符合 Hibernate 规范的配置文件,从而加速项目的启动和开发周期。 ... [详细]
  • 为了向用户提供虚拟应用程序,通常会在基础架构中部署StoreFront或Web Interface。为了确保安全的远程访问,通常需要在DMZ中配置Secure Gateway或Access Gateway。本文详细对比了这两种界面工具的功能特性,包括用户管理、安全性、性能优化等方面,为企业选择合适的解决方案提供了全面的参考。 ... [详细]
  • 本文详细介绍了使用C++实现插入排序算法的方法,并对其进行了优化。通过具体的代码示例,解释了插入排序的基本原理和优化技巧,包括交换两个元素的函数 `SwapTwo` 的实现。此外,文章还探讨了插入排序的时间复杂度和适用场景,为读者提供了深入理解该算法的全面指南。 ... [详细]
  • 在使用Block时,正确的声明方法和确保线程安全是至关重要的。为了保证Block在堆中分配,应使用`copy`修饰符进行声明,因为栈中的Block与栈的生命周期绑定,容易导致内存问题。此外,还需注意Block捕获外部变量的行为,以避免潜在的循环引用和数据不一致问题。建议深入研究相关文档,以掌握更多高级技巧和最佳实践。 ... [详细]
  • 利用树莓派畅享落网电台音乐体验
    最近重新拾起了闲置已久的树莓派,这台小巧的开发板已经沉寂了半年多。上个月闲暇时间较多,我决定将其重新启用。恰逢落网电台进行了改版,回忆起之前在树莓派论坛上看到有人用它来播放豆瓣音乐,便萌生了同样的想法。通过一番调试,终于实现了在树莓派上流畅播放落网电台音乐的功能,带来了全新的音乐享受体验。 ... [详细]
  • 本文全面解析了 gRPC 的基础知识与高级应用,从 helloworld.proto 文件入手,详细阐述了如何定义服务接口。例如,`Greeter` 服务中的 `SayHello` 方法,该方法在客户端和服务器端的消息交互中起到了关键作用。通过实例代码,读者可以深入了解 gRPC 的工作原理及其在实际项目中的应用。 ... [详细]
  • CAS 机制下的无锁队列设计与实现 ... [详细]
  • 概率与期望动态规划的深入探讨与应用分析
    本文深入探讨了概率与期望动态规划的基本原理及其在实际问题中的应用。概率是指某一事件发生的可能性大小,用P(A)表示。若某一事件的所有可能结果共有n种,且每种结果出现的概率相等,而事件A包含其中的m种结果,则该事件的概率P(A)为m/n。例如,在投掷骰子的情况下,如果事件A定义为掷出偶数点,由于共有3种偶数点(2、4、6),而总共有6种可能的结果,因此P(A)为1/2。文章进一步分析了概率与期望动态规划在复杂场景下的建模方法和求解策略,并通过具体实例展示了其在决策优化和风险管理中的应用价值。 ... [详细]
  • 在Python网络编程中,多线程技术的应用与优化是提升系统性能的关键。线程作为操作系统调度的基本单位,其主要功能是在进程内共享内存空间和资源,实现并行处理任务。当一个进程启动时,操作系统会为其分配内存空间,加载必要的资源和数据,并调度CPU进行执行。每个进程都拥有独立的地址空间,而线程则在此基础上进一步细化了任务的并行处理能力。通过合理设计和优化多线程程序,可以显著提高网络应用的响应速度和处理效率。 ... [详细]
  • 在 JavaScript 中,变量前的加号(+)符号用于将变量转换为数字类型。例如,在 `if (+valueDistance) {}` 语句中,加号的作用类似于 `Number(valueDistance)`,会根据 Number 函数的规则将变量转换为数值或 NaN。这种用法常用于确保变量在进行数值运算时不会出现类型错误。 ... [详细]
  • 虚拟机网络设置与数据库远程连接优化指南
    本文针对个人计算机上虚拟机网络配置与数据库远程连接的问题,提供了一套详细的优化指南。在探讨远程数据库访问前,需确保网络配置正确,特别是桥接模式的设置。通过合理的网络配置,可以有效解决因虚拟机或网络问题导致的连接失败,提升远程访问的稳定性和效率。 ... [详细]
  • 如何在CAD阅图软件中将PDF文件高效转换为CAD格式?
    如何在CAD阅图软件中将PDF文件高效转换为CAD格式? ... [详细]
  • 基于域名、端口和IP的虚拟主机构建方案
    本文探讨了在单台物理服务器上构建多个Web站点的虚拟主机方案,详细介绍了三种主要的虚拟主机类型:基于域名、基于IP地址和基于端口的虚拟主机。每种类型的实现方式及其优缺点均进行了深入分析,为实际应用提供了全面的技术指导。 ... [详细]
  • 《精通 jQuery》第六章:深入解析与实战应用
    《精通 jQuery》第六章:深入解析与实战应用本章详细探讨了 Ajax 技术的核心机制及其实际应用。Ajax 通过 XMLHttpRequest 对象实现客户端与服务器之间的异步数据交换,从而在不重新加载整个页面的情况下更新部分内容。这种技术不仅提升了用户体验,还提高了应用的响应速度和效率。此外,本章还介绍了如何利用 jQuery 简化 Ajax 操作,并提供了多个实战案例,帮助读者更好地理解和掌握这一重要技术。 ... [详细]
author-avatar
壹滒_918
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有