P1057

· · 题解

UPD:2019/7/7

主要更新了关于DP的讲解，使本文更适合初学者。

UPD:2020/2/12

由于似乎有人看不懂表是怎么打出来的，我就在咕了几个月之后来说明一下。

整理了文章内容，删去了一些无关言论。

改变码风，调整注释，并添加解法说明。

优化阅读体验，将过长且不很必要的代码转移到剪贴板中。节约读者滑滚轮时间。

正文

这道题明眼人都看得出有很多做法，比如搜索、DP等等，似乎还有人用了矩阵乘法。

总而言之，彰显出大佬的强大，但麻烦且对初学者非常不友好。

像我这种蒟蒻，只会打暴力的BFS。。

解释一下思路：先开一个结构体：

struct node
{
    int now,state;      //当前球的位置和传了几次
    node(int a,int b)   //这个是一个函数，可以在结构体队列中方便地进行元素入队，待会会讲到
    {
        now=a,state=b;
    }
};

最早我的想法就是，开这样一个队列，将当前球的状态（球传到到第几个人）的往左传和往右传的可能压进队列（特判一下1和n的情况），（当然作为显示传了几次的state要加一）然后扔掉队首元素。

完整代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,i;
long long ans;
struct node
{
    int now,state;          //now是当前球在谁手中，state是球被传了几次
    node(int a,int b)
    {
        now=a,state=b;
    }
};
queue <node> que;
void bfs(int x,int step)
{
    if(step==m)     //步数已经达到了上限
    {
        que.push(node(x,step));
        return;
    }               //特判1
    if(x==1)
    {
        que.push(node(n,step+1));
        que.push(node(2,step+1));
    }
    else if(x==n)   //特判n
    {
        que.push(node(n-1,step+1));
        que.push(node(1,step+1));
    }
    else
    {
        que.push(node(x-1,step+1));
        que.push(node(x+1,step+1));
    }
    return;
}
void all()          //统计函数，就是最后到了步数都达到上限的时候，统计所有球在1位置的情况
{
    while(!que.empty())
    {
        node xy=que.front();
        if(xy.now==1)
            ans++;
        que.pop();
    }
}
int main()
{
//  freopen("ball.in","r",stdin);
//  freopen("ball.out","w",stdout);
    cin>>n>>m;
    que.push(node(1,0));
    while(que.front().state!=m)
    {
        bfs(que.front().now,que.front().state);
        que.pop();
    }
    all();
    cout<<ans<<endl;
    return 0;
}

当然，各位dalao都知道，这种做法是不可能AC的。

为什么？（因为这是暴力枚举啊，连剪枝都没有）

来让我们加一个小小的剪枝。

我们可以判断一下，就是当前位置如果连一直往一个方向走都到不了位置1的话，那这个状态也就没用了，可以直接return掉。

贴上剪枝版的BFS中要添加的内容：

    if(x-(m-step)>1&&x-(m-step)<n)  //判断是不是到不了位置1
        return;

然后，我们输入数据“5 27”的答案是正确的，运行时间从未剪枝的29.65秒缩短到了26秒多

所以说，普通的搜索+优化是不可行的。

怎么办？

  1. 打表！

我第一个想到的方法。

暴力标程都出来了，不打表干嘛呢？有时间再去死磕DP正解啊

用于打表的程序：前往剪贴板查看

于是，就有了接下来的表：前往剪贴板查看

好了，我们的表已经出来了。提交，AC！

（话说洛谷的评测现在似乎每个测评点时间下限从以前的0ms提高到了2ms/3ms？不然打表程序一般情况下怎么可能需要几十ms的时间呢？）

  1. 高级优化

本来解法2和解法3都是没有的，直接就到DP了。

但是后来我回顾了一下以前做过的一道题：P1877 音量调节

这是我对该题的题解（已过审）：P1877

（宣传博客？算了不管了）

在P1877中，本来我的BFS也是过不了的，但是我后来想到一个优化方法，把BFS给过了，在洛谷的环境下用时28ms，也就是平均每个测试点2~3ms，这个已经和我交上去通过的DP程序差不多了（第一次24ms，后面又交了一次，29ms？）。

这个优化方法就是压缩/合并相同状态

状压DP

其实原理很简单：不再是每个状态用一次BFS，而是每一轮传球用一次BFS，在这一次BFS中将所有这轮传的球统一处理，先全部统计起来，最后统一入队。

这样子的话，我们的队列当中最多最多也只会有30个元素，因为每个位置最多会在当前队列中出现一次。这样空间和时间复杂度是不是就降下来了？

前往剪贴板查看

但是其实如果这么做的话，跟DP就没有本质上的区别了，所以似乎所有的方法最终都指向了DP。

  1. 记忆化搜索

记忆化搜索，我们教练是有专门针对这道题讲过的。懒得打，由于年代久远又抄不到教练的标程，而且我翻了翻题解，已经有别人的记搜过审了。oh yeah我可以不放标程了，诸位自行寻找吧

  1. DP

对于DP新手来说，打DP是一件很痛苦的事情。

有一个技巧（？）：要从找规律开始。

我们可以发现，任何一个位置都只能从左边和右边传过来，那么他只能从他左边和他右边的同学手上接到球，那球传到他手上的路径数是不是球传到他左边同学的路径数与球传到他右边同学的路径数之和？

有点绕，但是如果你是想认真学习的人，那么希望你能按下性子，认真理解一下这句话。

这样我们就可以列出我们的方程：

f[i][j]=f[i-1][j-1]+f[i-1][j+1]

为什么是这样？

让我们用手模拟一下（假设有5个人，传6次球，为了方便理解，我将其做成了一个环）：

在初始情况下，小蛮手中必然有且只有一个球，记为1；

第一轮传球后，小蛮必然将手中的球传给2号或5号同学，于是这两个同学各有1种方式接到球；

第二轮传球后，（如果上一轮小蛮将球传给2号）2号同学必然将球传给小蛮或3号，（如果上一轮小蛮将球传给5号），5号同学必然将球传给小蛮或4号，于是小蛮有2种情况接到球（分别从2号和5号手中）；

第三轮及其后以此类推。

我们据图可以发现，假设初始情况为第0行，小蛮为第1列，则有（从第1行开始）：

f[i][j]=f[i-1][j-1]+f[i-1][j+1];

只需要特判一下1和n就行了。

贴DP标程：

#include<bits/stdc++.h>
using namespace std;
int f[31][31],i,j,m,n;
int main()
{
    cin>>n>>m;
    f[0][1]=1;
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            if(j==1)
                f[i][j]=f[i-1][n]+f[i-1][2];
            else if(j==n)
                f[i][j]=f[i-1][1]+f[i-1][n-1];
            else
                f[i][j]=f[i-1][j-1]+f[i-1][j+1];
    cout<<f[m][1]<<endl;
    return 0;
}

最后，告诫大家：

DP是毒瘤，谁打谁知道。

要想不被毒，暴力少不了。