首页 > 代码库 > hdu4804（轮廓线dp）
hdu4804（轮廓线dp）
题意：给你一个n*m的矩阵(1<=n<=100,1<=m<=10)，矩阵里面分为空格和障碍物两种，现在用1*2,2*1,1*1的地板去铺满整个矩阵，且1*1地板所有个数的取值在[c,d]之间(1<=c<=d<=20)，问你一共有多少种方法铺满？
代码菜的抠脚，应该把状态转移改成update函数，这样就会好很多
1、我们设dp[cur][g][k]为当前情况已用了g个1*1的板子枚举状态为k的方案数。
2、假设当前(i,j)是障碍物的话，说明我(i,j)这个点不用填东西，并且(i,j)是东西的。
3、假设当前(i,j)是空格的话，我们分情况考虑下：
(1)假设(i,j)我不填东西，说明(i-1,j)是有东西的。
(2)假设(i,j)我填1*1，说明(i-1,j)是有东西的。
(3)假设(i,j)我填(2*1)，说明(i-1,j)是没有东西的。
(4)假设(i,j)我填(1*2)，说明(i,j-1)是没有东西的，(i-1,j)是有东西的。
1 #include<string> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<iostream> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 typedef long long ll; 10 const ll mod=1e9+7; 11 ll dp[2][1<<12][22]; 12 int n,m,C,D; 13 char map[105][105]; 14 int main() 15 { 16 //freopen("output.txt","w",stdout); 17 int i,j,k,num; 18 while(scanf("%d%d%d%d",&n,&m,&C,&D)!=EOF) 19 { 20 memset(dp,0,sizeof(dp)); 21 for(i=0;i<n;i++)scanf("%s",map[i]); 22 int cur=0; 23 dp[cur][(1<<m)-1][0]=1; 24 for(i=0;i<n;i++) 25 { 26 for(j=0;j<m;j++) 27 { 28 cur^=1; 29 memset(dp[cur],0,sizeof(dp[cur])); 30 for(k=0;k<(1<<m);k++) 31 { 32 for(num=0;num<=D;num++) 33 { 34 if(!dp[cur^1][k][num])continue; 35 if(map[i][j]==‘1‘) 36 { 37 if(j) 38 { 39 if((k&(1<<(m-1)))&&(k&1)) 40 { 41 dp[cur][(k<<1)^(1<<m)][num]+=dp[cur^1][k][num]; 42 dp[cur][(k<<1)^(1<<m)][num]%=mod; 43 if(num^D)dp[cur][((k<<1)^(1<<m))^1][num+1]+=dp[cur^1][k][num],dp[cur][((k<<1)^(1<<m))|1][num+1]%=mod; 44 } 45 else if((k&(1<<(m-1)))&&(!(k&1))) 46 { 47 dp[cur][(k<<1)^(1<<m)^3][num]+=dp[cur^1][k][num]; 48 dp[cur][(k<<1)^(1<<m)^3][num]%=mod; 49 dp[cur][(k<<1)^(1<<m)][num]+=dp[cur^1][k][num]; 50 dp[cur][(k<<1)^(1<<m)][num]%=mod; 51 if(num^D)dp[cur][((k<<1)^(1<<m))|1][num+1]+=dp[cur^1][k][num],dp[cur][((k<<1)^(1<<m))|1][num+1]%=mod; 52 } 53 else if((!(k&(1<<(m-1))))&&(k&1)) 54 { 55 dp[cur][(k<<1)^1][num]+=dp[cur^1][k][num]; 56 dp[cur][(k<<1)^1][num]%=mod; 57 } 58 else if((!(k&(1<<(m-1))))&&(!(k&1))) 59 { 60 dp[cur][(k<<1)^1][num]+=dp[cur^1][k][num]; 61 dp[cur][(k<<1)^1][num]%=mod; 62 } 63 } 64 else 65 { 66 if((k&(1<<(m-1)))) 67 { 68 dp[cur][(k<<1)^(1<<m)][num]+=dp[cur^1][k][num],dp[cur][(k<<1)^(1<<m)][num]%=mod; 69 if(num^D)dp[cur][(k<<1)^(1<<m)^1][num+1]+=dp[cur^1][k][num],dp[cur][(k<<1)^(1<<m)^1][num+1]%=mod; 70 } 71 else 72 { 73 dp[cur][(k<<1)^1][num]+=dp[cur^1][k][num]; 74 dp[cur][(k<<1)^1][num]%=mod; 75 } 76 } 77 } 78 else 79 { 80 if(k&(1<<(m-1)))dp[cur][(k<<1)^(1<<m)^1][num]+=dp[cur^1][k][num],dp[cur][(k<<1)^(1<<m)^1][num]%=mod; 81 } 82 } 83 } 84 } 85 } 86 ll ans=0; 87 for(i=C;i<=D;i++) 88 { 89 ans+=dp[cur][(1<<m)-1][i]; 90 ans%=mod; 91 } 92 printf("%lld\n",ans); 93 } 94 }
hdu4804（轮廓线dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。