成都网站建设 赢展,网页截图快捷键可拉动,中关村,嘉兴cms模板建站蒙德里安的梦想
算法标签
状态压缩dp
题目大意#xff1a;求把 NM的棋盘分割成若干个12 的的小长方形#xff0c;有多少种方案。
思路分析#xff1a; 首先#xff0c;注意到#xff0c;我们直接考虑如何切割整个棋盘为若干个1x2的长方形是比较困难的#xff0c;因此…蒙德里安的梦想
算法标签
状态压缩dp
题目大意求把 N×M的棋盘分割成若干个1×2 的的小长方形有多少种方案。
思路分析 首先注意到我们直接考虑如何切割整个棋盘为若干个1x2的长方形是比较困难的因此我们可以把整个棋盘划分为若干个1x1的小格子那么问题就转化为了用1x2的小长方形去将整个棋盘填充满总共有多少种方案。此外注意到当我们将所有横向的小长方形都已经摆放(填充)完成后所有纵向的小长方形的摆放方式也就唯一确定了那么总的方案数就等于摆完所有横向长方形的方案数。所以我们只用考虑如何枚举横向长方形的摆放即可
模型 这个问题属于状态压缩dp问题的第一大类基于连通性的dp也可以叫做棋盘式dp。我们首先考虑如何定义(设计)状态也就是如何进行状态表示。 我们按列来枚举横向小长方形的摆放情况。f为dp数组。若当前我们需要摆放的列是第i 列那么第i列在摆放的时候只和第i-1列有关(因为只有i-1列的小长方形可能伸到第i列影响第i 列的摆放)。因此我们设f[i][j]表示前i-1列已经摆放完毕(不能再改了)当前要对第i列进行横向小长方形的摆放且前一列伸出一个小方格是j 的情况下的方案数。如下图所示
j是一个n位的二进制数上图对应的j为01代表第i-1列第0行伸出了一个小方格(所以j的第0位为1)。那么这个状态表示的集合就是
所有前i-1列已经摆放完毕且第i-1列伸出小方格的状态为j的情况下的摆放方案
f[i][j]记录的是集合中的方案总数(根据题目所求来确定)
接下来考虑如何进行状态计算(转移)所谓状态计算就是对集合进行划分而划分的依据就是“最后一个不同点”。根据我们上面f[i][j]的定义第i-1列横向小长方形的摆放方案是确定的(因为二进制数j代表了其摆放的情况)所以最后一个不同点就是第i-2列的摆放情况。因此我们将依据第i-2列的摆放情况对f[i][j]所表示的大集合进行划分将它划分成1n个子集。但是这些子集不一定都可以转移过来因此我们需要判断哪些子集所对应的状态才可以转移到我们当前的状态。为了方便之后的表示我们设a为第i-1列的“摆放情况”b为第i-2列的”摆放情况”。那么合法的状态需要满足以下两个条件1ab0,即二者的二进制不能有某一位同时为1(意思是第i-2列和第i-1列不能在同一行同时摆放上横向的小长方形(同时伸出小格子)因为这样第i-2列伸出的小方格就会”阻碍”到第i-1列的摆放是不合法的)
2: 由于第i-1列横向的格子已经摆放完毕那么其纵向格子的摆放方式也已经确定所以我们摆完横向的小长方形后剩下连续的空格子的数量不能是奇数否则就不能通过摆放纵向小长方形将整个棋盘填满了。所以我们需要算出每个状态下连续0的个数。这个条件的判断可以通过”预处理完成”。
另外我们可以预处理出所有合法(能够进行状态转移的状态),方便后续状态的计算。
这样f[i][j]就等于所有能转移到它的状态所对应的方案数的总和。
我们最终的答案就是:f[m][0]。注意下标从0开始所以它代表所有前m–1列(也就是整个棋盘)已经摆完并且伸出格子的情况为0(没有伸出棋盘是合法的)的方案总数。并且dp数组的初始化为f[0][0]1(因为摆第0列时不存在前一列会伸出来也就表示当前列没有横着摆的小长方形所以只有都竖着摆放这一种情况)
c代码
#includeiostream
#includecstring
#includevector
using namespace std;
const int N12,M1N;
typedef long long LL;
int n,m,st[M];//st1表示当前状态是合法的
LL f[N][M];//极限状态下可能会爆int
vectorinttruestate[M];//二维数组truestate[i]中存储所有可以转移到状态i的状态方便通过循环递推计算出所有状态的值
//vectorvectorinttruestate(M);
int main()
{while(cinnm,n||m) //逗号表达式的值为逗号之后的值{for(int i0;i1n;i)//枚举所有状态判断其是否有连续奇数个0{st[i]1;int cnt0;//连续奇数0的个数for(int j0;jn;j)if(ij1)//i的第j位是1,前一段连续的0终止了{if(cnt1)//cnt为奇数{st[i]0;break;}cnt0; //继续统计下一段连续0的个数要将上一段的数量清零(实际上不清0也可以AC因为加一个偶数不会影响奇偶性(奇数会break))}elsecnt;if(cnt1)//判断最后一段连续0的个数的奇偶性st[i]0;}for(int i0;i1n;i)//计算出所有的truestate 这里i枚举的是状态定义中对应的第i-1列的情况j枚举的是第i-2列对应的情况{truestate[i].clear();for(int j0;j1n;j)if(!(ij)st[i|j])//只要二者有一位为1连续0就会被隔断,所以第状态定义中第i-1列实际的状态是i|jtruestate[i].push_back(j);}memset(f,0,sizeof(f));f[0][0]1;for(int i1;im;i)//枚举所有列for(int j0;j1n;j)//枚举所有状态for(auto k:truestate[j])//遍历所有可以转移到j的状态f[i][j]f[i-1][k];//状态计算(转移)coutf[m][0]endl;}return 0;
}时间复杂度分析dp问题的时间复杂度公式 状态数量× 状态转移(计算)
状态表示 f[i][j] 第一维i可取11第二维j二进制数可取2的11次方,根据乘法原理可计算出状态数量 状态转移 也是2的11次方(每个状态最多可划分成这么多个子集) 所以总的时间复杂度约等于4e7
