DpUVALive 6177The King's Ups and Downs

    练习赛的时候写了个爆搜，然后没跑出来 就不搞了， 田腿说用状压跑，打表。其实有能直接过的Dp吧。 下面是打表的Dp。。结果除了第一个 其余乘以2就行了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <string>
#include <iostream>
#include <map>
#include <cstdlib>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include<math.h>
using namespace std;
typedef long long LL;
LL n;
LL dp[1<<20][20][2];
LL dfs(LL state,LL pre,LL shang)
{
    if(~dp[state][pre][shang]) return dp[state][pre][shang];
    LL x=0;
    for(LL i=0;i<n;i++)
        if(state&(1<<i)) x++;
    if(x==n) return dp[state][pre][shang] = 1;
    LL ans=0;
    if(shang){
        for(LL i=pre+1;i<=n;i++)
        if(state&(1<<(i-1))) continue;
        else
        ans+=dfs(state|(1<<(i-1)),i,shang^1);
    }
    if(!shang){
        for(LL i=1;i<pre;i++){
            if(state&(1<<(i-1))) continue;
            ans+=dfs(state|(1<<(i-1)),i,shang^1);
        }
    }
    return dp[state][pre][shang]= ans;
}

int main()
{
    freopen("out.txt","w",stdout);
    for(n=1;n<=20;n++){
        memset(dp,-1,sizeof(dp));
        cout<<dfs(0,0,1)<<','<<endl;
    }
    return 0;
}