题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2045

题目描述

人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉,这可急坏了众多“Cole”(LELE的粉丝,即”可乐”),经过多方打探,某资深Cole终于知道了原因,原来,LELE最近研究起了著名的RPG难题:

有排成一行的n个方格,用红(Red)、粉(Pink)、绿(Green)三色涂每个格子,每格涂一色,要求任何相邻的方格不能同色,且首尾两格也不同色.求全部的满足要求的涂法.

以上就是著名的RPG难题.

如果你是Cole,我想你一定会想尽办法帮助LELE解决这个问题的;如果不是,看在众多漂亮的痛不欲生的Cole女的面子上,你也不会袖手旁观吧?

思路

这题我以前用过DFS来做果断超时= =

现在用递推来搞。

先看看题目,给的是三种颜色,容易得出
$$F(1)=3, F(2)=6, F(3)=6$$

  1. 现在求F(n),按最后一个位置颜色分析,只能有一种颜色可选,因为第一格占了一种颜色,第n-1格占了一种颜色,此时有$F(n-1)*1种$涂色方案。举个例子,假设涂四格,RPG,…,F(3)种情况,那么RPG(P)只能涂一种颜色,即$F(3)*1$
  2. 然而上述情况中,并不包含第n-1格和第一格颜色一致的情况,那么再来分析最后两个位置颜色,设第n-1格涂的颜色和第一格涂的颜色一致(若不一致的话就和F(n-1)的情况冲突,这步就没有意义了),那么第n格就有两种颜色可选(除去和第一格颜色一致的颜色),即$F(n-2)*2$,举个例子,假设涂四格,RP…,F(2)种情况,那么设第3格涂的颜色和第一格颜色一直即RPR,那么第四个有两种颜色可选,即F$(2)*2$,

综合上面两种情况,$F(n)=F(n-1)*1+F(n-2)*2$。

现在推出一般式,设有K种颜色,容易得出

$$F(1)=K, F(2)=A(K,2)=K*(K-1), F(3)=A(K,3)=K*(K-1)*(K-2)$$
  1. 现在求F(n),按最后一格颜色分析,只能有k-2种颜色可选,因为第一格占了一种颜色,第n-1格占了一种颜色,此时有$F(n-1)*(k-2)$种涂色方案,例子可参考上述例子。
  2. 然而上述情况并不包含第n-1格和第一格颜色一致的情况,那么再来分析最后两个位置颜色,设第$n-1$格涂的颜色和第一格涂的颜色一致(若不一致的话就和$F(n-1)$的情况冲突,这步就没有意义了),那么第n格就有k-1种颜色可选(除去和第一格颜色一致的颜色),即$F(n-2)*(k-1)$。例子可参考上述例子。

综上所述,一般式,设有K种颜色,那么

$$F(n)=(K-2)*F(n-1)+(K-1)*F(n-2)$$

据说n很大的时候可以用矩阵乘法快速幂进行加速。。。

$$ \begin{pmatrix} F(n) \\ F(n-1) \end{pmatrix} = \begin{pmatrix} k-2 & k-1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F(n-1)\\ F(n-2) \end{pmatrix} = \begin{pmatrix} k-2 & k-1 \\ 1 & 0 \end{pmatrix}^{n-2} \begin{pmatrix} F(1)\\ F(2) \end{pmatrix}$$

AC代码

/*************************************************************************
    > File Name: 2045.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Tue 26 May 2015 11:39:15 AM CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int main()
{
#ifdef Oj
#endif
    double f[51];
    f[1]=3;
    f[2]=6;
    f[3]=6;
    for(int n=4;n<=50;n++)
        f[n]=2*f[n-2]+f[n-1];
    int n;
    while(cin >> n)
        printf("%.lf\n",f[n]);
    return 0;
}