算法设计与分析-10304 平面域着色

 小技巧，当题目问到方案数时，此题目几乎可以确定是动态规划类题目，动态规划也是用递归的思想来考虑如和实现分治（将大问题变小），读者可以尝试将递归代码改写成递推代码（动态规划）。

解题思路：递归基础题，难点在于圆环。观察D1和Dn，由于环相邻，它们颜色必不相同。此时如果Dn-1和D1颜色相同，那么Dn的颜色共有K-1中选择，且Dn的颜色无论是什么都不会影响到D2......Dn-2。那么我们将D1DnDn-1想象成是一个域，此时问题就从规模n变成了规模n-2。

 另一种情况Dn-1和D1颜色不同，此时Dn就 只有K-2中颜色选择，当然，无论它选哪一种颜色，对其他位置都不会有任何影响。此时我们可以认为Dn-1是最后一个元素，认为Dn-1可以与D1相邻（颜色不同）。此时问题规模变为n-1。

因此递推公式为 f(n)=(k-1)*f(n-2)+(k-2)*f(n-1)

还有一些无法填充特殊情况必须要考虑进去，

（1）n>1&&k==1 颜色不足以填充，答案0；

（2）n%2==1&&k==2 奇数个格子只有2中颜色，那么D1和Dn会同色；

递归结束条件也有三种情况，请阅读代码。(友情提示：本代码已开启防抄袭模式，请勿复制粘贴）

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
long long f(int n,int k)
{
    if(n==1)
        return k;
    else if(n==2)
        return k*(k-1);
    else if(n==3)
        return k*(k-1)*(k-2);
    return (k-1)*f(n-2,k)+(k-2)*f(n-1,k);
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j,n,k;
    cin>>n>>k;
    if(n>1&&k<1||n%2=1&&k==2)
    {
        cout<<0;
        return 0;
    }
    cout<<f(n,k);
    return 0;
}