题目简述

输入 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;
}