首页 > 腾讯4.4笔试 k种颜色小球放n个盒子
头像
Sologala
编辑于 2021-04-05 13:26
+ 关注

腾讯4.4笔试 k种颜色小球放n个盒子

题目简述

输入 n(盒子数量), k(k种颜色,数量不限的小球), 每个box 放置一个小球,相邻两个盒子可以颜色一样,但是连续三个或者大于三个盒子不能颜色一样。

解法

排列组合解法

两个盒子可以颜色一样,可以把它们看做是一个box,绑定起来。
对于有0个被绑定的盒子

对于有1个被绑定给的盒子

不是一般性,

解释一下 代表了选中两个被绑定的box,颜色一样,且不违背题目条件的排列种数 表示,当选择了i个box绑定在一起之后,所有的盒子数量为 , 从 中选择出i个表示颜色相同。

代表了长度为 的序列,两两都不相同的前提下,k中颜色的球的排列数目。
第一个球可以选择k中,第二个球因为要和第一个球不同,于是只有 k-1 种,后面同理。

所有最后的答案为:


代码就不放了,按照公式写就好了.

动态规划

思考一下,我们在放置 第i个盒子的时候,是有两种情况存在,一是当前盒子的颜色与上一个盒子的颜色相同,另外一种是不同。我们分别用 表示不同, 表示相同。

转移方程的推导

如下图所示,我们可以知道如果在放置第二个box的时候保证和上一个一样,且不违背题目要求的话,上一个盒子一定是上上一个盒子是不同的,最后在第二个盒子重复第一个盒子的小球。于是
图片说明

当保证第二个盒子的颜色与上一个不同的时候,其实需要考虑只有一个盒子的时候的所有状态,且在第二个盒子上加上与第一个盒子小球颜色不同的小球,也就是

图片说明

值得注意的是, 图中只考虑了两种颜色小球的情况,当出现k中颜色小球的时候,

int main(int argc, const char **argv) {
  int n, k;
  cin >> n >> k;
  int f[2][2] = {{k, 0}};

  for (int i = 1; i <= n; ++i) {
    int cur = (i) % 2;
    int pre = (i - 1 + 2) % 2;
    f[cur][0] = f[pre][1];
    f[cur][1] = (f[pre][0] + f[pre][1]) * (k - 1);
  }

  cout << f[n %2][0] + f[n%2][1] << endl;
  return 0;
}

全部评论

(5) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐