题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1260

题目描述:

题目大意:每一个人去电影票买票,有两种买票方法:1、自己单人买;2、与前面的人一起买;Joe是售票员,他想要早点下班,因此需要你编程序计算他能下班的最早时间。

解题思路:首先用一个数组a来存放每个人自己一个人买票所需时间,再用一个数组dou来存从第二个人开始,每个人与前面一个人合并买票所需时间,因为第一个人的前面不可能有人了(除了售票员Joe,哈哈),所以第一个人的买票时间是确定了的为a[1]。采用动态规划来解决此问题,动态转移方程式为

dp[i]=min(dp[i-1]+a[i],dp[i-2]+dou[i]);

即:第i个人买票所花的最少时间等于min(  前面i-1个人 买票所花时间  加上 第i个人(自己) 买票所花时间, 前面的i-2个人 买票所花时间 加上 第i个人与第i-1个人(自己与前面那人)合并买票所花时间);

代码实现:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int dp[];
int main()
{
int n,a[],k,dou[];//a数组存放单人买票所花时间,dou数组存放与前面那人一起买票所花时间
scanf("%d",&n);
while(n--)
{
memset(dp,,sizeof(dp));
memset(a,,sizeof(a));
memset(dou,,sizeof(dou));
scanf("%d",&k);
for(int i=;i<=k;i++)
scanf("%d",&a[i]);
for(int i=;i<=k;i++)
scanf("%d",&dou[i]);
dp[]=a[];//第一个人买票时间是固定了的,因为他的前方不再可能有人与他一起买票了
for(int i=;i<=k;i++)//从第二个人开始遍历,找出最终的买票时间
dp[i]=min(dp[i-]+a[i],dp[i-]+dou[i]);
int h=dp[k]/;///记录最终的时间
int m=dp[k]%/;
int s=dp[k]%;
printf("%02d:%02d:%02d%s\n",(+h)%,m,s,(h+)%>?" pm":" am");//输出时间hh:mm:ss的简单操作
}
return ;
}

最新文章

  1. Axure 资料搜集
  2. sdk 更新的时连接不上dl-ssl.google.com解决办法
  3. RPI学习--环境搭建_默认启动桌面/终端修改
  4. mysql 5.6 oom 图
  5. 设置css三种方法的优先级
  6. iso 开发学习--简易音乐播放器(基于iPhone4s屏幕尺寸)
  7. html 实现网址链接
  8. iOS UITextField垂直居中
  9. 【 js 模块加载 】深入学习模块化加载(node.js 模块源码)
  10. mapfile中关于栅格数据的processing项说明
  11. 分布式、集群、微服务、SOA 之间的区别
  12. TypeError: &#39;_io.TextIOWrapper&#39; object does not support item assignment
  13. 如何批量添加图片到ppt的方法
  14. Android开发 ---代码创建选项菜单、隐藏菜单项、菜单的生命周期,菜单按钮图标设置、搜索框、xml中设置子菜单
  15. OpenCV Python : No drawMatchesknn function
  16. HTML中的元素分类
  17. Direct2D教程IV——笔刷(Brush)对象
  18. win7(64)未在本地计算机上注册 Microsoft.Jet.OLEDB.4.0 提供程序
  19. 【AppCan 开发者】移动信息化随想
  20. 使用node_redis进行redis数据库crud操作

热门文章

  1. Spring源码解读
  2. android fragment解析
  3. Linux搜索查找类指令
  4. Centos7.5 防火墙设置
  5. BackBone结合ASP.NET MVC实现页面路由操作
  6. Linux内存管理3---分页机制
  7. ERROR 1067 (42000): Invalid default value for &#39;created_time&#39;【转】
  8. Json对象和字符串互相转换 数据拼接 JSON使用方式
  9. c++ 引用方式传递数组
  10. Centos6安装FreeSWITCH 1.5时./configure问题解决记录