首页 > 代码库 > bzoj1725[Usaco2006 Nov]Corn Fields牧场的安排*
bzoj1725[Usaco2006 Nov]Corn Fields牧场的安排*
bzoj1725[Usaco2006 Nov]Corn Fields牧场的安排
题意:
n*m的土地,有的土地不能种草。求有多少种种草方案使得没有两块草地相邻。n,m≤12。
题解:
先预处理出存在草地左右相邻的不合法状态,然后状压dp。f[i][S]表示当前处理第i行上一行状态为S,则f[i][S]=sum(f[i+1][T]),T满足没有草种在不能种的地上且不与上一行上下相邻同时不存在左右相邻。本来按道理来说这种方法是会超时的,然而似乎本题数据弱。
代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define mod 100000000 6 using namespace std; 7 8 int f[2][5000],t[20],n,m,x,y,ans; bool bad[5000]; 9 int main(){10 scanf("%d%d",&n,&m); inc(i,1,n){t[i]=0; inc(j,1,m){int x; scanf("%d",&x); t[i]+=((!x)<<(j-1));}}11 inc(i,0,(1<<m)-1){12 inc(j,1,m-1)if((i&(1<<(j-1)))&&(i&(1<<j))){bad[i]=1; break;}13 }14 x=0; y=1; inc(i,0,(1<<m)-1)if(!(i&t[n])&&!bad[i])f[x][i]=1;15 for(int i=n-1;i>=1;i--){16 inc(j,0,(1<<m)-1){17 f[y][j]=0; if(!(j&t[i])&&!bad[j]){inc(k,0,(1<<m)-1)if(!(k&j))f[y][j]=(f[y][j]+f[x][k])%mod;}18 }19 swap(x,y);20 }21 inc(i,0,(1<<m)-1)ans=(ans+f[x][i])%mod; printf("%d",ans); return 0;22 }
20160908
bzoj1725[Usaco2006 Nov]Corn Fields牧场的安排*
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。