我是有用dp做的,做完之后看网上大多人都是推出公式,反正我是没看出来
dp[i][j],i表示第i列放入一竖条,j表示放入的竖条是什么形状,j一共有5种情况,dp就表示这个i表示第i列放入一个j类型竖条有几种摆放方法
如图 0~4表示j的五种状态
然后就有递推公式
dp[i][0]=dp[i-1][0]+dp[i-1][3]+dp[i-1][4]
dp[i][1]=dp[i-1][0]+dp[i-1][3]+dp[i-1][4]
dp[i][2]=dp[i-1][0]+dp[i-1][3]+dp[i-1][4]
dp[i][3]=dp[i-1][1]
dp[i][4]=dp[i-1][2]
最后dp[i][0]+dp[i][3]+dp[i][4]就是答案
代码如下
对了其中还有一个好囧的事,就是没完全初始化,eclipse就是编译不了 唉!!!
import java.util.*; import java.math.*; public class Main{ public static void main(String[] args){ Scanner scan=new Scanner(System.in); BigDecimal[][] dp= new BigDecimal [320][10]; dp[0][0]=new BigDecimal (1); dp[1][0]=new BigDecimal (1); dp[1][1]=new BigDecimal (1); dp[1][2]=new BigDecimal (1); dp[1][3]=new BigDecimal (0); dp[1][4]=new BigDecimal (0); dp[0][1]=new BigDecimal (0); dp[0][2]=new BigDecimal (0); dp[0][3]=new BigDecimal (0); dp[0][4]=new BigDecimal (0); for(int i=2;i<=300;i++){ dp[i][0]=dp[i-1][4].add(dp[i-1][0].add(dp[i-1][3])); dp[i][1]=dp[i-1][4].add(dp[i-1][0].add(dp[i-1][3])); dp[i][2]=dp[i-1][4].add(dp[i-1][0].add(dp[i-1][3])); dp[i][3]=dp[i-1][1]; dp[i][4]=dp[i-1][2]; } while(scan.hasNext()){ int in=scan.nextInt(); System.out.println(dp[in][0].add(dp[in][3].add(dp[in][4]))); } } }