首页 > 代码库 > DpUVALive 6177The King's Ups and Downs
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;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。