学步园

从昨天下午写到现在，终于算是A了，实在是很郁闷啊！

这道题看到能想到的就是状态压缩dp了，刚开始写了一个很暴力的，开了两个数组，dp1[i][j]用来记录第i行头朝上的，dp2[i][j]用来记录第i行头朝下的,然后位运算按照条件进行dp的，超时就不用说了，但是一直wa就让我很郁闷啊！！改了一个晚上，还是那样，然后看了别人的题解说只开一个数组只记录头朝下的进行判断，然后又写但是只解决了超时的问题，然后的然后，想想换个记录三角形头朝上的，因为那样最后求了一半的时候合起来比较好判断，然后竟然ac啦！高兴啊，但是那个为什么错就不知道了。。。

思路：dp[i][j]用来记录第i行三角形头朝上状态为j的一共的个数，dp[i][j]+=dp[i-1][k]如果状态j和上一行的状态k相容，在这里我是用一个函数进行判断的，是将数据拆成一位一位的然后进行判断。最后sum+=dp[2*n][i]*dp[2*n][i];因为上面的半边合下面的半边完全相同，就可以直接简化了，下面是代码！

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<climits>
#include<map>
using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)
#define repf(i,n,m) for(int i=(n); i<=(m); ++i)
#define repd(i,n,m) for(int i=(n); i>=(m); --i) 
#define ll long long
#define arc(a) ((a)*(a))
#define inf 100000
#define exp 0.000001
#define N  1<<13
ll dp[20][N];

bool fun(int n,int x,int y)
{ 
	int sign=-1;//sign用来记录这一位的前一个状态的。 
	int flag=true;
	rep(i,n)
	{
        int m=(y>>i)&1; 
		if(m==1 && sign==-1)
		{
			sign=(x>>i)&1;
			if(i==n-1 || sign==0) flag=false;
			sign=-1;
		}
		else if(m==1 && sign==1)
		{
			sign=(x>>i)&1;
		}
		else if(m==1 && sign==0)
		{
             sign=(x>>i)&1;
             if(sign==0 || i==n-1) flag=false;
             sign=-1;
        }
		else if(m==0 && sign==-1)
		{
			sign=(x>>i)&1;
		}
		else if(m==0 && sign==1)
		{
              flag=false;
		}
		else if(m==0 && sign==0)
			sign=(x>>i)&1;
		if(flag==false)
			return flag;
	}
	return true;
}

int main()
{ 
	int n;
	int test=0;
	while(cin>>n)
	{
       if(test!=0) printf("\n");
       test++;
		memset(dp,0,sizeof(dp)); 
		dp[n][(1<<n)-1]=1;
		repf(i,n+1,2*n)
		{ 
			rep(j,1<<(i-1))//shang
			{ 
				if(dp[i-1][j]==0) continue;
		        rep(k,1<<i)//下
                {  
					if(fun(i,j,k))//判断两种状态是否相容 
					{ 
						dp[i][k]+=dp[i-1][j];
                     }
                  }
			} 
		}
		ll sum=0;
		rep(i,1<<(2*n))
		 rep(j,1<<(2*n))
		  if((i^j)==0)
		 sum+=dp[2*n][i]*dp[2*n][j]; //求到一半直接简化 
		cout<<sum<<endl;
	}
   return 0;
}