题目
试题3:恐怖的奴隶主(bob)
源代码:bob.cpp
输入文件:bob.in
输出文件:bob.out
时间限制:1s
空间限制:512MB
【题目描述】
小L热衷于undercards.
在undercards中,有四个格子。每个格子要么是空的,要么住着一只BigBob。
每个BigBob有一个不超过k的血量;血量减到0视为死亡。那个格子随即空出。
当一只BigBob受到伤害后,假如它没有死亡且剩余血量为t,它会从左数第一个空格处召唤一只血量为a[t]的BigBob;若没有空格,则不会召唤。
法术R定义为:从左往右,对每个BigBob造成一点伤害;假如有BigBob死亡,重复上述效果。
聪明的小L发现,在某些情况下,当他发动法术R时,游戏会陷入循环。
他想求出这样的初始情形有多少种。
【输入输出说明】
输入一个正整数k;
随后一行k-1个正整数,表示a[1]~a[k-1];
输出一个整数,表示答案。
【样例输入】
2
2
【样例输入】
34
【样例解释】
Bigbob最多有2血,满血bigbob受伤会召出新的。
循环的初始状态有:
(2,1,0,0),(0,2,0,0),(1,2,0,0),(2,0,1,0),(2,1,1,0),(0,2,1,0),(1,2,1,0),(2,2,1,0),(0,0,2,0),(1,0,2,0),(0,1,2,0),(1,1,2,0),(2,1,2,0),(2,1,0,1),(0,2,0,1),(1,2,0,1),(0,2,1,1),(1,2,1,1),(0,0,2,1), (1,0,2,1),(0,1,2,1),(1,1,2,1),(2,1,2,1),(0,2,2,1),(1,2,2,1),(2,1,0,2),(0,2,0,2),(1,2,0,2),(2,0,1,2),(2,1,1,2),(0,2,1,2),(1,2,1,2),(2,2,1,2),(2,1,2,2)
共34种。
【数据范围】
对于30%的数据,k≤5;
对于70%的数据,k≤10, a[i]=k;
对于100%的数据,k≤15, 1≤a[i]≤k。
分析
代码
#include<iostream> #include<cstring> #include<algorithm> using namespace std; long long k,s[40],t[11000],ans=0; bool flag[16][16][16][16],flag_ans[16][16][16][16]; inline void dfs(int x) { if(x==5) { int a=s[1],b=s[2],c=s[3],d=s[4]; memset(flag,0,sizeof(flag)); while(1) { flag[a][b][c][d]=1; bool fflag=0; if(a==1 || b==1 || c==1 || d==1) fflag=1; a=max(a-1,0); if(a) { if(!b) b=t[a]; else if(!c) c=t[a]; else if(!d) d=t[a]; } if(b==1) fflag=1; b=max(b-1,0); if(b) { if(!a) a=t[b]; else if(!c) c=t[b]; else if(!d) d=t[b]; } if(c==1) fflag=1; c=max(c-1,0); if(c) { if(!a) a=t[c]; else if(!b) b=t[c]; else if(!d) d=t[c]; } if(d==1) fflag=1; d=max(d-1,0); if(d) { if(!a) a=t[d]; else if(!b) b=t[d]; else if(!c) c=t[d]; } if(a+b+c+d==0 || !fflag) return; if(flag[a][b][c][d]) { //cout<<s[1]<<s[2]<<s[3]<<s[4]<<endl; ans++; return; } } } for(int i=0;i<=k;i++) { s[x]=i; dfs(x+1); } } int main() { cin>>k; for(int i=1;i<k;i++) cin>>t[i]; dfs(1); cout<<ans; return 0; }