「优质题解」机器人塔

这道题的地址，想尝试的小伙伴可以来试哦：

https://www.dotcpp.com/oj/problem1837.html

思路：

题意：A的下面只能AA或BB，B的下面只能是AB或BA（各位想到二进制的异或没有）；

如果：有1个A和2个B，那么有三种方案：

那么就可以用0代表A，1代表B;

还要一点要说，题目的意思是从下向上摆（下面多上面少），为了写程序方便（二维数组从一行开始），我们从从上向下摆，显然结果是一样的。

（注意：下面是按反过了的模型说的（倒三角型））

那么只要知道第一行的数据，就可以依次更新下面的数据（反对角线方向从上向下）；也就是说只用枚举一行的所有可能就可以了，第2行开始的结果都是根据上一行来的。

如何枚举一行：第一行每一个位置不是1就是0，每一个位置每次从0开始枚举，到1结束；枚举方向从左到右；

例如：拿样例来说吧：1个A，2个B也就是1个0，2个1；

（注意：这里枚举0，1是在第一行，其他行都是根据第一行来更新的）

0 // 第一行第一个位置为0，此时不用更新

0 0 // 第一行第二个位置为0，此时更新第二行

1 // 不合格（约束：1个0）

0 1 // 第一行第二个位置为1，此时更新第二行

1 // 合格，方案数加一

1 // 第一行第一个位置为1，此时不更新

1 0 // 第一行第二个位置为0，此时更新

1 // 合格，方案数加1

1 1 // 第一行第二个位置为1，此时更新

0 // 合格，方案数加1

此时已经枚举完毕，总方案数为3。

（注意：一直都是枚举的第一行的每一种方案，其他行都是根据第一行更新得到的）

如何统计A,B的个数（也就0，1的个数）：加入用cnt计数，每次枚举的时候直接cnt+=枚举的那个位置上的数，如果是1那就加上了，是0就相当于没加，那这不就是统计了1的个数吗！！0的个数用当前规模的总个数减去1的个数就可以了。

注意事项:

题目中提到：测试数据都合法。也就是说可以算出一行都多少个数字；

* * * *

* * *

* *

*

上面的这个图，就是每次更新的范围，所有*的总个数就是A，B的总和；

在知道了A，B的个数之和，就可以算出第一行有几个数（人）；

怎么算？等差数列求和，公差为1；前n项和就是 （1 + n）* n / 2

假设第一行只有一个数（x=1），计算以边前n项和看是否相等，如果相等那么第一行就有x个数，如果不x+1

，然后看是否相等，最后就得到了第一行能放几个数（x）。

注意：题目的要点就是枚举第一行有多少种可能，每种情况用来去更新其他行。

若觉得文章对你有帮助，随手转发分享，也是我们继续更新的动力

扫描二维码关注我们