不容易系列之(3)—— LELE的RPG难题

此博客链接：https://www.cnblogs.com/ping2yingshi/p/12449143.html

不容易系列之(3)—— LELE的RPG难题（92min）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2045

Problem Description

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

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

以上就是著名的RPG难题.

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

Input

输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成，(0<n<=50)。

Output

对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。

Sample Input

Sample Output

题解：

方法：数学推导。

思路：由题目已知，当n=1时，可以有3种结果，当n=2时，可以有6种结果，当n=3时，可以有6种结果，当求n个方格，实际可以由n-1个方格的结果加上到达n个方格还有几种涂法。题目要求第一种颜色不能和最后一种颜色相同，相邻的颜色不能相同，当有n个方格时，第一个方格不能和第n个方格相同，第n-1个方格不能和第n个方格相同，而第n个方格涂的颜色数可以由第n-1个颜色数得来，分两种情况：

1.第一个方格颜色和第n-1个颜色涂的一样，此时第n个方格颜色可以有两种涂法，而第n-1种涂法实际上等于第n-2个方格的涂法，所以这种情况有2*（n-2）种涂法。

2.第一个方格颜色和第n-1个颜色涂的不一样，此时第n个方格只有一种颜色可涂，所以这种情况有n-1种涂法。

代码如下：

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
  int n;
  while(~scanf("%d",&n))
  {
    long long colnum[10000];
    int i;
    colnum[1]=3;
    colnum[2]=6;
    colnum[3]=6;
    for(i=4;i<=n;i++)
    {
       colnum[i]=colnum[i-1]+2*colnum[i-2];
    } 
    printf("%lld
" ,colnum[n]);   
  }              
  return 0;
}

一开始用java写的，我在编辑器运行没有错误，但是提交说编辑错误，目前没有找到错误。(经过师兄的指点，java提交代码类名需要时Main，以前都是c提交的，这下知道了）

代码如下：

import java.util.Scanner;


public class test {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
       Scanner scan=new Scanner(System.in);
      
       while(scan.hasNext())
       {
           int n=scan.nextInt();
           long [] cornum=new long[60];
           cornum[1]=3;
           cornum[2]=6;
           cornum[3]=6;
           for(int i=4;i<=n;i++)
           {
              cornum[i]=cornum[i-1]+2*cornum[i-2]; 
           }
           System.out.println(cornum[n]);
   
       }

    }

}