首页 > 代码库 > 【XY1371】细菌分裂
【XY1371】细菌分裂
Description
某科学家在培养皿（可以认为培养皿无限大）的正中间0时刻放置了一个分裂能力极强的细菌，它每隔一段时间就会进行分裂。具体地说，当初始的细菌被激活后，它会向前移动T1格(含起点)，之后会分裂成两个，方向分别为原方向向左和向右偏移45°，两个细菌分别沿自己的方向移动T2格后再次分裂，……，n个周期后，细菌停止了分裂。现在Smart想知道有多少个格子被细菌污染了(注意，只要细菌经过的格子就会被污染，一个格子多次经过算一次，一个格子可以同时存在多个细菌，具体见样例及样例说明)。
Input
第一行一个正整数n，代表周期数。
接下来n个非负整数Ti，代表各个周期的长度。
接下来n个非负整数Ti，代表各个周期的长度。
Output
输出一行，包含一个整数表示被污染的格子数。
Sample Input
3
2
3
3
2
3
3
Sample Output
20
Sample Explanation
Hint
5%的数据：n=1；
25%的数据：n≤2；
55%的数据：n≤20；
另有25%的数据：n≤27，T1=T2=…..=Tn；
100%的数据：n≤50，T1+T2+…+Tn ≤200。
25%的数据：n≤2；
55%的数据：n≤20；
另有25%的数据：n≤27，T1=T2=…..=Tn；
100%的数据：n≤50，T1+T2+…+Tn ≤200。
----------------------------------------------------------------------------------
算法：记忆化搜索
题解：
这题用记忆化搜索，状态f(t,x,y,d)，其中t表示时间，(x,y)表示细菌所处位置，d表示方向。
如果(x,y)被第一次访问，那么答案+1
每当到了一个周期，就转向就可以了~
细节处理可能有点繁琐，慢慢做就好啦
代码：
#include<cstdio>#include<iostream>using namespace std;const int N=55,M=206;int dx[8]={-1,-1,0,1,1,1,0,-1};int dy[8]={0,-1,-1,-1,0,1,1,1};int ans=0,tot=0;bool f[206],vis[406][406],used[206][406][406][8];void dfs(int t, int x, int y, int d){ if(t>tot) return; if(used[t][x][y][d]) return; //记忆化 used[t][x][y][d]=true; if(!vis[x][y]) { ans++; vis[x][y]=true; } if(f[t]) //转向45度 { dfs(t+1,x+dx[(d+1)%8],y+dy[(d+1)%8],(d+1)%8); dfs(t+1,x+dx[(d+7)%8],y+dy[(d+7)%8],(d+7)%8); } else dfs(t+1,x+dx[d],y+dy[d],d);}int main(){ int n,t; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&t); tot+=t; f[tot]=true; } dfs(1,tot,tot,0); printf("%d",ans);}
【XY1371】细菌分裂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。