poj 2411 状态压缩dp

时间:2021-10-09 09:35:12

思路:将每一行看做一个二进制位,那么所有的合法状态为相邻为1的个数一定要为偶数个。这样就可以先把所有的合法状态找到。由于没一层的合法状态都是一样的,那么可以用一个数组保存。由第i-1行到第i行的状态转移是dp[i][now|num[j]]+=dp[i-1][k],其中now为(1<<m)-1-k;也就是把k中含有0的变1,1边0。k为第i-1行的所有二进制状态,转移条件是k&num[j]==num[j]。唯一注意的是,最后一行的条件是k^num[j]==0.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Maxn 13
#define inf 0x7fffffff
using namespace std;
__int64 dp[Maxn][<<Maxn];
int num[<<Maxn],cnt1,cnt2,graphic[Maxn],co,n,m;
void dfs(int j,int f)
{
int i;
if(j==m)
{
int sum=;
if(f)
graphic[j]=;
else
graphic[j]=;
for(i=m;i>=;i--)
sum+=graphic[i]*(<<(m-i));
num[++cnt2]=sum;
return ;
}
if(!f)
{
graphic[j]=;
dfs(j+,);
graphic[j]=;
dfs(j+,);
}
else
{
graphic[j]=;
dfs(j+,);
}
}
int main()
{
int i,j,k;
while(scanf("%d%d",&n,&m)!=EOF,n||m)
{
if((n*m)%)
{
printf("0\n");
continue;
}
if(n==)
{
printf("1\n");
continue;
}
memset(dp,,sizeof(dp));
graphic[]=;
cnt2=;
dfs(,);
for(i=;i<=cnt2;i++)
dp[][num[i]]=;
int temp=<<m;
temp--;
for(i=;i<=n-;i++)
{
for(j=;j<=cnt2;j++)
{
for(k=;k<=temp;k++)
{
if((k&num[j])==num[j])
{
int now=temp-k;
dp[i][now|num[j]]+=dp[i-][k];
}
}
}
}
__int64 ans=;
for(j=;j<=cnt2;j++)
{
for(k=;k<=temp;k++)
{
if((k^num[j])==)
ans+=dp[i-][k];
}
}
printf("%I64d\n",ans);
}
return ;
}

poj 2411 状态压缩dp的更多相关文章

  1. Mondriaan&&num;39&semi;s Dream&lpar;POJ 2411状态压缩dp&rpar;

    题意:用1*2的方格填充m*n的方格不能重叠,问有多少种填充方法 分析:dp[i][j]表示i行状态为j时的方案数,对于j,0表示该列竖放(影响下一行的该列),1表示横放成功(影响下一列)或上一列竖放 ...

  2. POJ 1185 状态压缩DP(转)

    1. 为何状态压缩: 棋盘规模为n*m,且m≤10,如果用一个int表示一行上棋子的状态,足以表示m≤10所要求的范围.故想到用int s[num].至于开多大的数组,可以自己用DFS搜索试试看:也可 ...

  3. POJ 1185 状态压缩DP 炮兵阵地

    题目直达车:   POJ 1185 炮兵阵地 分析: 列( <=10 )的数据比较小, 一般会想到状压DP. Ⅰ.如果一行10全个‘P’,满足题意的状态不超过60种(可手动枚举). Ⅱ.用DFS ...

  4. poj 2923&lpar;状态压缩dp&rpar;

    题意:就是给了你一些货物的重量,然后给了两辆车一次的载重,让你求出最少的运输次数. 分析:首先要从一辆车入手,搜出所有的一次能够运的所有状态,然后把两辆车的状态进行合并,最后就是解决了,有两种方法: ...

  5. poj 2688 状态压缩dp解tsp

    题意: 裸的tsp. 分析: 用bfs求出随意两点之间的距离后能够暴搜也能够用next_permutation水,但效率肯定不如状压dp.dp[s][u]表示从0出发訪问过s集合中的点.眼下在点u走过 ...

  6. poj 3254 状态压缩DP

    思路:把每行的数当做是一个二进制串,0不变,1变或不变,找出所有的合法二进制形式表示的整数,即相邻不同为1,那么第i-1行与第i行的状态转移方程为dp[i][j]+=dp[i-1][k]: 这个方程得 ...

  7. POJ 2411 状态压缩递,覆盖方案数

    无非就是横着放与竖着放,状态中用1表示覆盖,0表示未覆盖. #include <iostream> #include <vector> #include <algorit ...

  8. POJ 3254 状态压缩 DP

    B - Corn Fields Crawling in process... Crawling failed Time Limit:2000MS     Memory Limit:65536KB    ...

  9. POJ 3691 &lpar;AC自动机&plus;状态压缩DP&rpar;

    题目链接:  http://poj.org/problem?id=3691 题目大意:给定N个致病DNA片段以及一个最终DNA片段.问最终DNA片段最少修改多少个字符,使得不包含任一致病DNA. 解题 ...

随机推荐

  1. java多线程-锁

    自 Java 5 开始,java.util.concurrent.locks 包中包含了一些锁的实现,因此你不用去实现自己的锁了.但是你仍然需要去了解怎样使用这些锁. 一个简单的锁 让我们从 java ...

  2. CoInitialize浅析一

    大家都知道程序中若要使用COM组件则必须要先调用CoInitialize,该函数主要是用来初始化COM运行环境.但这个函数的作用域是以线程为单位还是以进程为单位呢?也许大家已经通过测试程序摸索出答案, ...

  3. EASYUI 表单&lpar;FORM&rpar;用法

    提交表单 $('#addform').form('submit', { url: '/Admin/AdminUser/AddAdminUser', onSubmit: function () { re ...

  4. iOS:访问地址薄

    地址簿的访问 介绍: 地址簿(Address Book)是一个共享的联系人信息数据库.任何iOS应用程序都可以使用.通过提供常用联系人信息,而不是让每一个应用程序管理独立的联系人列表,可改善用户体验. ...

  5. HttpContext

    HttpContext 类:封装有关个别 HTTP 请求的所有 HTTP 特定的信息.也有人叫上下文信息. 1.生存周期:从客户端用户点击并产生了一个向服务器发送请求开始---服务器处理完请求并生成返 ...

  6. Java - 反射机制&lpar;Reflection&rpar;

    Java - 反射机制(Reflection)     > Reflection 是被视为 动态语言的关键,反射机制允许程序在执行期借助于 Reflection API 取得任何类的       ...

  7. asp&period;net mvc 注册中的邮箱激活功能实现(一)

    基本流程图 注册页面就不再写出,现在将发送邮件的代码粘贴出来 public ActionResult SendEmial() { ; string validataCode = System.Guid ...

  8. USACO 2&period;3 Cow Pedigrees

    Cow Pedigrees Silviu Ganceanu -- 2003 Farmer John is considering purchasing a new herd of cows. In t ...

  9. Java 多线程详解(五)------线程的声明周期

    Java 多线程详解(一)------概念的引入:http://www.cnblogs.com/ysocean/p/6882988.html Java 多线程详解(二)------如何创建进程和线程: ...

  10. Excel大批量数据导出

    package com.tebon.ams.util; import lombok.extern.slf4j.Slf4j;import org.apache.poi.openxml4j.excepti ...