热门标签 | 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


推荐阅读
  • 二维码的实现与应用
    本文介绍了二维码的基本概念、分类及其优缺点,并详细描述了如何使用Java编程语言结合第三方库(如ZXing和qrcode.jar)来实现二维码的生成与解析。 ... [详细]
  • publicclassBindActionextendsActionSupport{privateStringproString;privateStringcitString; ... [详细]
  • 数据类型--char一、char1.1char占用2个字节char取值范围:【0~65535】char采用unicode编码方式char类型的字面量用单引号括起来char可以存储一 ... [详细]
  • 本文将从基础概念入手,详细探讨SpringMVC框架中DispatcherServlet如何通过HandlerMapping进行请求分发,以及其背后的源码实现细节。 ... [详细]
  • importjava.io.*;importjava.util.*;publicclass五子棋游戏{staticintm1;staticintn1;staticfinalintS ... [详细]
  • 我的读书清单(持续更新)201705311.《一千零一夜》2006(四五年级)2.《中华上下五千年》2008(初一)3.《鲁滨孙漂流记》2008(初二)4.《钢铁是怎样炼成的》20 ... [详细]
  • 本文介绍了如何通过C#语言调用动态链接库(DLL)中的函数来实现IC卡的基本操作,包括初始化设备、设置密码模式、获取设备状态等,并详细展示了将TextBox中的数据写入IC卡的具体实现方法。 ... [详细]
  • 本文详细介绍了C++中的构造函数,包括其定义、特点以及如何通过构造函数进行对象的初始化。此外,还探讨了转换构造函数的概念及其在不同情境下的应用,以及如何避免不必要的隐式类型转换。 ... [详细]
  • 回顾两年前春节期间的一个个人项目,该项目原本计划参加竞赛,但最终作为练习项目完成。独自完成了从编码到UI设计的全部工作,尽管代码量不大,但仍有一定的参考价值。本文将详细介绍该项目的背景、功能及技术实现。 ... [详细]
  • 解决Visual Studio Code中PHP Intelephense误报问题
    PHP作为一种高度灵活的编程语言,其代码结构可能导致Intelephense插件在某些情况下报告不必要的错误或警告。自1.3.3版本起,Intelephense引入了多个配置选项,允许用户根据具体的工作环境和编程风格调整这些诊断信息的显示。 ... [详细]
  • 在处理大数据量的SQL分页查询时,通常需要执行两次查询来分别获取数据和总记录数。本文介绍了一种优化方法,通过单次查询同时返回分页数据和总记录数,从而提高查询效率。 ... [详细]
  • 本文通过一个具体的实例,介绍如何利用TensorFlow框架来计算神经网络模型在多分类任务中的Top-K准确率。代码中包含了随机种子设置、模拟预测结果生成、真实标签生成以及准确率计算等步骤。 ... [详细]
  • 嵌套列表的扁平化处理
    本文介绍了一种方法,用于遍历嵌套列表中的每个元素。如果元素是整数,则将其添加到结果数组中;如果元素是一个列表,则递归地遍历这个列表。此方法特别适用于处理复杂数据结构中的嵌套列表。 ... [详细]
  • HTML前端开发:UINavigationController与页面间数据传递详解
    本文详细介绍了如何在HTML前端开发中利用UINavigationController进行页面管理和数据传递,适合初学者和有一定基础的开发者学习。 ... [详细]
  • 本文详细探讨了BCTF竞赛中窃密木马题目的解题策略,重点分析了该题目在漏洞挖掘与利用方面的技巧。 ... [详细]
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社区 版权所有