DP就是每次在原序列右边加一个city的时候 (此时n个city) 只要看前一个状态 (n-1个city) 最右边的city的情况
也就是记录n个city时的三个状态 xxxV xxx> xxx<
xxxV 和 xxx< 的数量和就是要求的结果, xxx>是记录一下如果允许向右流水那么方案的数量
状态转移即为右图
然后dp[100]结果超过long long, 于是用BigInteger, 写这个报告的原因也是第一次用Java交OJ..

代码:

import java.math.*;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		BigInteger dp[][]=new BigInteger[101][2];
		dp[1][0]=BigInteger.ONE;
		dp[1][1]=BigInteger.ZERO;
		for(int i=2;i<=100;i++) {
			dp[i][0]=dp[i-1][0].add(dp[i-1][0]).add(dp[i-1][1]);
			dp[i][1]=dp[i-1][0].add(dp[i-1][1]);
		}
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()) {
			int a=sc.nextInt();
			System.out.println(dp[a][0].add(dp[a][1]));
		}
	}
}