首页 > 代码库 > 【轮廓线DP】POJ2411-Mondriaan's Dream
【轮廓线DP】POJ2411-Mondriaan's Dream
今天美国的院士过来讲课XD以为会很无聊但是谜之好听,而且英语基本上都听懂了的样子?(´▽`)
逃到图书馆来写解题报告
【题目大意】
给出一个m*n的方格,用2*1的骨牌覆盖有几种情况。
【思路】
最基础的轮廓线DP。分为三种情况:
(1)向上放,必须要满足上面的格子没有被放,且当前不在首行。→新状态=旧状态删去首位,末尾为1;
(2)向左放,必须要满足左边的格子和上面的格子都没有放,且当前不在首列。→新状态=旧状态删去首位,末两位微1;
(3)不放,必须满足上面的格子没有放。新状态=旧状态删去首位,末尾为0。
*轮廓线状压的表示不是按照纵坐标大小从左到右,而是按照从左到右,从上至下的顺序(K4..K0)来的:D
【错误点】
一开始把cur的变换写到最里面一重循环去了orz
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 typedef long long ll; 7 const int MAXN=11; 8 ll dp[2][1<<MAXN]; 9 10 void solve(int m,int n)11 {12 if (m<n) swap(m,n);13 int cur=0;14 memset(dp,0,sizeof(dp));15 dp[cur][(1<<n)-1]=1;16 for (int i=1;i<=m;i++)17 for (int j=1;j<=n;j++)18 {19 cur^=1;20 /*cur要放在第二重循环后面,一开始写在了三重循环里面*/ 21 memset(dp[cur],0,sizeof(dp[cur]));22 /*不要忘了要清空当前状态*/23 for (int k=0;k<=(1<<n)-1;k++)24 {25 //上放26 if (i!=1 && !(k&(1<<(n-1))))27 {28 int now=(((k<<1)|1)&((1<<n)-1));29 dp[cur][now]+=dp[1-cur][k];30 } 31 //不放32 if (k&(1<<(n-1)))33 {34 int now=((k<<1)&((1<<n)-1));35 dp[cur][now]+=dp[1-cur][k];36 }37 //左放 38 if (j!=1 && (k&(1<<(n-1))) && !(k&1))39 {40 int now=(((k<<1)|3)&((1<<n)-1));41 dp[cur][now]+=dp[1-cur][k];42 } 43 }44 }45 cout<<dp[cur][(1<<n)-1]<<endl;46 }47 48 int main()49 {50 int m,n;51 while (scanf("%d%d",&m,&n))52 {53 if (m==n && n==0) break;54 solve(m,n);55 }56 return 0;57 }
【轮廓线DP】POJ2411-Mondriaan's Dream
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。