首页 > 其他 > 详细

DpUVALive 6177The King's Ups and Downs

时间:2014-08-16 14:59:50      阅读:331      评论:0      收藏:0      [点我收藏+]

    练习赛的时候写了个爆搜,然后没跑出来 就不搞了, 田腿说用状压跑,打表。其实有能直接过的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;
}

 

DpUVALive 6177The King's Ups and Downs,布布扣,bubuko.com

DpUVALive 6177The King's Ups and Downs

原文:http://www.cnblogs.com/yigexigua/p/3916362.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!