1489 蜥蜴和地下室

2023-07-16 09:58:51

思路：先把最左和最右的干掉，剩下的再一起dfs。dfs的时候注意当第cur-1个死了之后（而第cur个不要求必须死）才向后面搜索第cur+1个。

当前的第cur个可以被扔在自己身上的火球，也可被扔在第cur+1个的火球干掉。

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include <set>
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include <string>
14 #include 
15 #include 
16 #define x first
17 #define y second
18 #define pb push_back
19 #define mp make_pair
20 #define lson l,m,rt*2
21 #define rson m+1,r,rt*2+1
22 #define mt(A,B) memset(A,B,sizeof(A))
23 #define mod 1000000007
24 using namespace std;
25 typedef long long LL;
26 const int N=2e5+10;
27 const int inf = 0x3f3f3f3f;
28 const LL INF=0x3f3f3f3f3f3f3f3fLL;
29 int x[N];
30 int n,a,b,ans,res_2=inf;
31 
32 
33 void dfs(int cur,int num)
34 {
35     int p=0,q;
36     if(cur==n-1)
37     {
38         ans=min(ans,num);
39         return;
40     }
41     if(x[cur-1]<0)dfs(cur+1,num);
42 
43     if(x[cur-1]>=0)
44     {
45         p=x[cur-1]/b+1;
46         x[cur-1]-=p*b;
47         x[cur]-=p*a;
48         x[cur+1]-=p*b;
49         dfs(cur+1,num+p);
50         x[cur-1]+=p*b;
51         x[cur]+=p*a;
52         x[cur+1]+=p*b;
53     }
54     q=x[cur]/a+1;
55     if(x[cur]>=0&&q>p)
56     {
57         for(int i=p+1;i<=q;i++)
58         {
59             x[cur-1]-=i*b;
60             x[cur]-=i*a;
61             x[cur+1]-=i*b;
62             dfs(cur+1,num+i);
63             x[cur]+=i*a;
64             x[cur+1]+=i*b;
65             x[cur-1]+=i*b;
66         }
67     }
68 }
69 int main()
70 {
71 #ifdef Local
72     freopen("data.txt","r",stdin);
73 #endif
74     int p=0,q=0;
75     cin>>n>>a>>b;
76     ans=inf;
77     for(int i=0; i"%d",&x[i]);
78     p=x[0]/b+1;
79     x[0]-=p*b;;
80     x[1]-=p*a;
81     x[2]-=p*b;
82     if(x[n-1]>=0)
83     {
84         q=x[n-1]/b+1;
85         x[n-2]-=q*a;
86         x[n-3]-=q*b;
87         x[n-1]-=q*b;
88     }
89     dfs(1,0);
90     if(ans==inf)ans=0;
91     cout<endl;
92 #ifdef Local
93     cerr << "time: " << (LL) clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
94 #endif
95 }

View Code

转载于:https://www.cnblogs.com/27sx/p/6266128.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！

标签：技术

上一篇 > Swift之父Chris Lattner将从Apple离职，加入特斯拉
下一篇 > Jquery validate验证表单时多个name相同的元素只验证第一个的问题

Duilib中list控件支持ctrl和shif多行选中的实现

[ICML2015]Batch Normalization:Accelerating Deep Network Training by Reducing Internal Covariate Shif

win10系统微软输入法于eclipse ctrl+shif+f冲突间接处理办法

Codeforces Round #259 (Div. 2) B. Little Pony and Sort by Shif

读LDD3，内存映射与DMA--PAGE_SHIF…

VMware虚拟机安装XP【要先分区，再设置BOOT 启动CD，shif+上移】

更换iBus五笔的左与右Shif

sublime ctrl+shif+f 没用解决办法

idea 对 ctrl + z 的撤销是 ctrl + shif + z

计算机最早的设计师应用于,计算机应用基础选择题doc.doc

win10自带截图神器：Win+Shift+S

Python基础之文件目录操作

python简述目录_Python基础之文件目录操作(示例代码)

tp5 如何做数据采集

任务2-7(服务器字体+阿里巴巴矢量库)

html标签（1)：h1~h6,p,br,pre,hr

TI 电量计介绍与芯片选型指南

几款TI电源芯片简介

TI DSP芯片C2000系列读取FLASH数据

德州仪器(Ti)平台嵌入式开发基础

TI三相电机智能栅极驱动芯片特点分类

省选模拟（12.08） T3 圈圈圈圈圈圈圈圈

Hadoop生态圈技术栈（上）

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之6.Impala交互式查询

小猿圈之Linux下Mysql 操作命令

大数据Hadoop生态圈常用面试题

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之4.Hive DDL、DQL和数据操作

备战Noip2018模拟赛11（B组）T3 Monogatari 物语

【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码

NYOJ 78 圈水池

递归问题跑道汽车绕圈问题 Python实现

Hadoop生态圈（三）：MapReduce

1489 蜥蜴和地下室

相关文章