当前位置: 首页 > news >正文

建设彩票网站多少钱网站关键词搜索

建设彩票网站多少钱,网站关键词搜索,食品类建设网站的目的,真实的企业管理培训课程文章目录 前言一、题目二、分析三、代码总结 前言 这题目出得很有意思哈,打劫也是很有技术含量滴!不会点算法打劫这么粗暴的工作都干不好。 提示:以下是本篇文章正文内容,下面案例可供参考 一、题目 题目名称: 打家…

文章目录

  • 前言
  • 一、题目
  • 二、分析
  • 三、代码
  • 总结


前言

这题目出得很有意思哈,打劫也是很有技术含量滴!不会点算法打劫这么粗暴的工作都干不好。
在这里插入图片描述


提示:以下是本篇文章正文内容,下面案例可供参考

一、题目

题目名称:
打家劫舍

题目描述:
一个小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

输入描述:
输入一个正整数n代表房屋的数量(n≤100),接着输入n个非负整数代表每间房屋的现金数量

输出描述:
小偷能偷取的最大金额。

示例1
输入
4
1 2 3 1

输出
4

二、分析

我们假设只有三个房间,事情就很简单了。做为专业小偷,我们知道,房屋编号是从0开始的,只能偷1号房屋或0号+2号房屋。为了取得最大战果,我们分别去看了看每个房屋能偷到多少。出门比较一下,就知道结果了。
我们逛完了三个房屋,现在站在第2号房屋门口来思考一下,就是选择0和2,或选1的问题。
我们把0+2能偷到的钱先记在2号房屋门上,把1号能偷到的钱记在1号门上,然后去看看3号房屋有多少钱可偷。这样1、2、3号房屋又成了一个同样的选择…
我们不停的在门上记录能偷到的钱,不停的用同样的方法选择。
拿示例来说,我们在1号房屋门上记上2毛,2号房屋门上记上4毛(0号加2号),然后和3号房屋来比较,显然4毛大于1号的2毛加3号的1毛。侦察完成,就偷0号加2号了!
再找个长点的例子:
1 2 3 2 9 1 2
同样先在1号房屋门上记上2毛,2号房屋门上记4毛(0号+2号),侦察完3号房屋后,就成了:
2 4 2 9 1 2
继续侦察下一家:
4 4 9 1 2
4 (13) 1 2
(13) 5 2
5 (15)
(15)
最后偷得15毛!

三、代码

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>using namespace std;int solution(int n, std::vector<int>& vec){int result=0;// TODO:vector<int> tmp={vec[0], max(vec[0], vec[1])};if(n==1) return tmp[0];if(n==2) return tmp[1];for (int i=2; i<n; ++i){tmp[i] = max(tmp[i-1], tmp[i-2]+vec[i]);}result = tmp[n-1];return result;
}int main() {int n;std::vector<int> vec;std::cin>>n;std::string line_0, token_0;getline(std::cin >> std::ws,line_0);std::stringstream tokens_0(line_0);while(std::getline(tokens_0, token_0, ' ')){vec.push_back(std::stoi(token_0));}int result = solution(n,vec);std::cout<<result<<std::endl;return 0;

max(vec[0], vec[1])这一句解决了前二个房屋的选择,因为第二个房屋我们必须选前两个中最大的。如果0号是最大的,就把1号变成0号一样,再来继续选择。
举例来看:
7 1 1 2
侦察前二个房屋后就是:
7 7 1 2
然后7 8 2
最后9
如果是这样的:
1 7 2 1
侦察前二个后就还是:
1 7 2 1
所以初始化的时候一定要考虑清楚!

总结

所谓动态规划:就是将问题划分为一系列子问题,求各子问题的最优解,然后以自底向上的方式递归地从子问题的最优解构造出整个问题的最优解。
在本例中,我们把n个房屋不停的当作三个房屋来处理。所以我们设计了一个tmp数组来存储过程数据。
动态规划和分治法有点像,都是把复杂问题分解成简单的小问题。
不过动态规划的子问题之间不是独立的,子问题的解往往会在下一个选择中被使用。
而分治法,一般会把一个复杂的问题分解成若干个独立的子问题,求解子问题后再合成本问题的解。今天的 “小艺照镜子” (本专栏的另一篇文章有详解)就是用分治法解的。

http://www.hrbkazy.com/news/24488.html

相关文章:

  • 网站建设责任分工品牌整合营销推广
  • 易语言做网站登录简单网页设计模板html
  • 网站建设办法谷歌优化排名公司
  • 商务网站建设一万字互联网销售平台
  • windows部署wordpress上海官网seo
  • 手机号注册网站java成品网站
  • 网站建设源代码广告营销顾问
  • 怎样设计自己网站域名排名seo公司哪家好
  • 欧美做的爱爱网站游戏优化大师手机版
  • 网站开发作品网络营销策划书800字
  • 做英文题的网站新媒体运营哪个培训机构好
  • 公司网站建设开源平台网站怎么推广出去
  • 广州荔湾网站制作十大经典事件营销案例
  • 中关村手机报价大全手机排行跟我学seo从入门到精通
  • 优化网站制作竞价培训课程
  • html5网站用什么软件成都百度推广代理公司
  • 两学一做网站专栏怎么设置郑州网站建设公司排名
  • 东莞市做网站厂房网络推广平台
  • wordpress image.php河南智能seo快速排名软件
  • 做报废厂房网站怎么做网站性能优化的方法有哪些
  • phpcms动态网站模板推广类软文
  • 金湖网站设计google 优化推广
  • 企业网站备案流程北京百度seo工作室
  • 网站建设官网免费模板怎么引流怎么推广自己的产品
  • 公司网站域名如何续费合肥网络关键词排名
  • 曲阳路街道网站建设怎么联系地推公司
  • wordpress导入tumblr网站如何做seo推广
  • 有没有免费的crm系统班级优化大师使用指南
  • 天动力网站开发企业网站推广方案策划
  • 自建商城网站有哪些平台seo关键词排名优化怎么样