題目

　　猛戳看題

分析

　　講題快luo！（逃

　　2019.9.5 17:00 本人現(xiàn)場表演什么叫蔡講題，歡迎拍磚。:)

　　暫時不開放PPt下載。

　　總之用dp[i][j]來表示對于前i行中，第i行采用第j種狀態(tài)時可以得到的可行方案總數(shù)。

　　dp[i][j]=dp[i-1][k₁]+dp[i-1][k₂]+…+dp[i-1][k_n]（k_n即為上一行可行方案的編號，上一行共有n種可行方案）

　　ans=dp[m][k₁]+dp[m][k₂]+…+dp[m][k_n]（k_n為最后一行可行方案的編號）

代碼

#include<bits/stdc++.h> using namespace std; #define Mod 100000000 int n,m,tot,ans;//v[i]//第i行整行的情況。 int dp[20][500],s[500],v[20];//dp對于前i行，每行有前j種可能方案時的解，s[i]存儲每行所有可行的方案。 int main() {scanf("%d%d",&n,&m);for(int i=0;i<(1<<m);i++) if((i&(i<<1))==0) s[++tot]=i;//記錄不相鄰的狀態(tài)。for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int a;scanf("%d",&a);//讀入該地塊是否可放。if(a==0) v[i]+=1<<j-1;//整行的二進制。}}dp[0][1]=1;for(int i=1;i<=n;i++){for(int j=1;j<=tot;j++)//判斷第i行假如按方案j放的話行不行。{if(s[j]&v[i]) continue;//判斷上一行與其狀態(tài)是否滿足。for(int k=1;k<=tot;k++){if(s[j]&s[k]) continue;dp[i][j]=(dp[i][j]+dp[i-1][k])%Mod;}}}for(int i=1;i<=tot;i++){if(s[i]&v[n]) continue;ans=(ans+dp[n][i])%Mod;}printf("%d",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/DARTH-VADER-EMPIRE/p/11468692.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1725 牧场的安排的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。