恐怖的奴隶主（bob）

佚名 6年前 (2019-05-08) 随笔 771人围观抢沙发百度已收录

题目描述

小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

样例输出

提示

【样例解释】
Bigbob最多有2血，满血bigbob受伤会召出新的。循环的初始状态有：
(2,1,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),(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),(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)
共31种。
【数据范围】
对于30%的数据，k≤5；对于70%的数据，k≤10, a[i]=k；对于100%的数据，k≤15, 1≤a[i]≤k。

解析：

在orz了石神和陈神后（如果你是SRY同学那么可以默默地离开了），蒟蒻终于非独立自主地做出了这道题。。。首先我们搂一眼这玩意，一看就是个深搜吗。。。k<=15啊~，此时不搜更待何时呢。。。四个空格，首先根据题意，我们要先去枚举四个格子里的数字，直接dfs即可，接下来我们去考虑一下如何判定，由于只有四个空格，我们完全可以开一个pd数组，而pd[a][b][c][d]==1就代表出现过第一个格子为a......第四个格子为d的这种情况（蒟蒻太懒，dalao请自行脑补）; 由于每次都得重新来，所以每次都要清空。。（我最开始怕RE，开了个50*50*50*50的数组，每次清空费了大量时间。。。【感谢伟大的石神帮我调了出来。。。】）然后只要按照规则来就好嘞~~~,如果有被杀死的，那就接着来，如果四个都被杀死了，就返回，还有一点要注意的是，这个pd（）函数里的数组不能和dfs排列的数组混了，因为是按序枚举，你把它改了，但是dfs函数不知道呀，，，还是接着枚举，下面给大家看看标准的错误代码：

bool pd1[50][50][50][50],f;
void pd()
{
    memset(pd1,0,sizeof(pd1));
    while(1)
    {
        f=0;
        pd1[gz[1]][gz[2]][gz[3]][gz[4]]=1;
        for(int i=1;i<=4;i++)
        {
            if(gz[i]==1)f=1;
            if(gz[i]>=1)gz[i]--;
            for(int j=1;j<=4;j++)
            {
                if(i==j)continue;
                if(gz[j]==0)
                {
                    gz[j]=a[gz[i]];
                    break;
                }
            }
        }
        if(gz[1]+gz[2]+gz[3]+gz[4]==0||f==0)
        {
            return;
        }
        if(pd1[gz[1]][gz[2]][gz[3]][gz[4]])
        {
            total++;
            return;
        }
    }
}
void dfs(int t)
{
    for(int i=0;i<=k;i++)
    {
        gz[t]=i;
        if(t==4)pd();
        else dfs(t+1);
    }
}

　　这个程序，又T又WA，可谓是WA,T两开花~，今年下半年中美合拍的西游记即将正式开机。。。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

最后上AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int k,a[20],gz[5],total,s,now[5];
bool pd1[16][16][16][16],f;//pd不能开太大，否则会T
inline void pd()
{
    memset(pd1,0,sizeof(pd1));
    /*cout<<gz[1]<<" "<<gz[2]<<" "<<gz[3]<<" "<<gz[4]<<endl;*/
    for(int i=1;i<=4;i++)gz[i]=now[i];//不能用排列的数组，否则会WA
    while(1)
    {
        f=0;
        pd1[gz[1]][gz[2]][gz[3]][gz[4]]=1;
        for(int i=1;i<=4;i++)
        {
            if(gz[i]<1) continue;
            gz[i]--;
            if(gz[i]==0)
            {
                f=1;
                continue;
            }
            for(int j=1;j<=4;j++)
            {
                if(i==j)continue;
                if(gz[j]==0)
                {
                    gz[j]=a[gz[i]];
                    break;
                }
            }
        }
        if(gz[1]+gz[2]+gz[3]+gz[4]==0||!f)return;
        if(pd1[gz[1]][gz[2]][gz[3]][gz[4]])
        {
            total++;
            return;
        }
    }
}
inline void dfs(int t)//生成四个格子的排列
{
    if(t==5)
    {
        pd();
        return;
    }
    for(int i=0;i<=k;i++)
    {
        now[t]=i;
        dfs(t+1);
    }
}
int main()
{
    cin>>k;
    for(int i=1;i<=k-1;i++)cin>>a[i];
    dfs(1);
    cout<<total;
    return 0;
}

　　时间复杂度最大为O(15*15*15*15*(memset函数速度蒟蒻不会算+10(pd函数while(1)运行的平均次数)）≈ O(8100000);稳~