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

自己做游戏网站网站页面

自己做游戏网站,网站页面,做网站需要什么语言,wordpress $authordata题意: 如图,一列未知的区域长度为n(≤1000),给出第二列的数字,求区域中雷的排列有多少种。 Solution: 搜索。这题看上去1000的范围很大,实际上加上合理的剪枝,状态数会变…

题意:

  

如图,一列未知的区域长度为n(≤1000),给出第二列的数字,求区域中雷的排列有多少种。

 

 


Solution:

  搜索。这题看上去1000的范围很大,实际上加上合理的剪枝,状态数会变得非常非常少。

     一个雷最多能影响3个格子,直接从上往下枚举这个地方有没有雷。有雷的话给影响的格子的数字减一。

      出现负数,或枚举到第k个位置了,第k-2个位置的数不为0的时候都是可以退出的。

      这样的搜索策略使得我们几乎不会做无用功,最多向下一层就回到了正确的方向。

 

实际上代码也只用了15ms

#include <iostream>
using namespace std;
int n, ans;
int s[1009];void dfs ( int x )
{if ( x - 2 > 0 && s[x - 2] != 0 ) return;if ( x == n + 1 ) {if ( s[n] == 0 ) ++ans;return ;}dfs ( x + 1 );int flag = 0;for ( int i = -1; i <= 1; ++i ) {if ( ( x + i > 0 && x + i <= n ) && --s[x + i] < 0 ) flag = 1;}if ( !flag ) dfs ( x + 1 );for ( int i = -1; i <= 1; ++i ) {if ( x + i > 0 ) ++s[x - i];}
}
int main()
{cin >> n;for ( int i = 1; i <= n; ++i ) {cin >> s[i];}dfs ( 1 );cout << ans << endl;
}
View Code

 

  然而分析复杂度的时候我发现。。。实际上如果我们确定了第一个格子有没有雷,就可以推断出下面所有的情况!

      所以只需要枚举第一个格子有没有雷就行了。显然答案的范围也在[0,2]。

  由此可以见上面的搜索算法的时间复杂度其实也是O(n)的。

转载于:https://www.cnblogs.com/keam37/p/4673658.html

http://www.lbrq.cn/news/2411551.html

相关文章:

  • 国外市场网站推广公司国内10大搜索引擎
  • .net做网站教程网络营销产品的特点
  • 进口外贸网站有哪些网站流量
  • 电子商务网站建设系统功能站内推广有哪些方式
  • 如何用自己公司网站做邮箱企业推广方法
  • 沈阳网站seo网站备案查询工信部官网
  • 网站获取访客文职培训机构前十名
  • 做英德红茶的网站竞价恶意点击犯法吗
  • 帮人负责做网站叫什么工作购买域名
  • 电子商务网站建设基本步骤品牌广告和效果广告
  • 网页设计师好吗广州网站优化页面
  • 网站常用文件夹seo刷排名公司
  • 做网站前端用什么关键词查询工具有哪些
  • 医疗企业vi设计公司百度seo优化包含哪几项
  • 上海做衣服版的网站高端网站建设制作
  • 赌博类网站开发中国旺旺(00151) 股吧
  • 成都网站建设索q479185700免费发广告的平台有哪些
  • 专做化妆品网站百度的链接
  • 阿里云云主机做网站北京seo推广公司
  • 火车头自动发布wordpress标签福州seo优化排名推广
  • 制作微信网站模板seo排名工具
  • 怎么做返利网站广州网络运营课程培训班
  • 网站开发和嵌入式开发今日疫情最新数据
  • 5免费网站建站关键词智能调词工具
  • 网站建设需求文档模板下载一键生成网页
  • 如何自己搭建一个个人网站百度客服
  • 中国江西网官方网站百度站长中心
  • 经典网站设计案例营销公司网站
  • 龙川网站建设怎样申请网站
  • wordpress文章专题插件平台seo什么意思
  • Web开发:ABP框架12——中间件Middleware的创建和使用
  • 金仓数据库:融合进化,智领未来——2025年数据库技术革命的深度解析
  • C/C++ 详谈结构体大小计算(内存对齐)
  • 一维数组练题习~
  • 30天打牢数模基础-卷积神经网络讲解
  • 费曼学习法