题目链接:http://poj.org/problem?id=1185

很裸的状压,考虑对于一行用二进制储存每一种的状态,但是状态太多了做不了。

观察到有很多状态都是不合法的,于是我们预处理出合法的状态,发现只有60种,然后随便DP一下就可以了。

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N,M;
char G[][];
int s[],cnt[],scnt=,ban[];
int f[][][];
int main(){
memset(ban,,sizeof(ban));
memset(f,,sizeof(f));
memset(cnt,,sizeof(cnt));
memset(s,,sizeof(s));
scanf("%d%d",&N,&M);
for(int i=;i<=N;i++) scanf("%s",G[i]);
for(int i=;i<=N;i++)
for(int j=;j<M;j++)
if(G[i][j]=='H')
ban[i]|=(<<j);
int tmp=<<M;
for(int i=;i<tmp;i++){
bool flag=true;
for(int j=;j<M;j++){
int tmp=((i&(<<j))>)+((i&(<<j+))>)+((i&(<<j+))>);
if(tmp>){
flag=false;
break;
}
}
if(flag){
s[++scnt]=i;
for(int j=;j<M;j++)
if(i&(<<j))
cnt[scnt]++;
}
}
for(int i=;i<=scnt;i++)
if((s[i]&ban[])==)
f[][][i]=cnt[i];
for(int i=;i<=scnt;i++)
if((s[i]&ban[])==)
for(int j=;j<=scnt;j++)
if((s[i]&s[j])==&&(s[j]&ban[])==)
f[][j][i]=max(f[][j][i],f[][][j]+cnt[i]);
for(int i=;i<=N;i++)
for(int j=;j<=scnt;j++)
if((s[j]&ban[i-])==)
for(int k=;k<=scnt;k++)
if((s[j]&s[k])==&&(s[k]&ban[i-])==)
for(int t=;t<=scnt;t++)
if((s[j]&s[t])==&&(s[k]&s[t])==&&(s[t]&ban[i])==)
f[i][k][t]=max(f[i][k][t],f[i-][j][k]+cnt[t]);
int Ans=;
for(int i=;i<=scnt;i++)
for(int j=;j<=scnt;j++)
Ans=max(Ans,f[N][i][j]);
printf("%d\n",Ans);
return ;
}

最新文章

  1. W7无法更新
  2. CSS3之让背景图片全部显示
  3. Hive与数据库的异同
  4. Groovy读取properties及txt
  5. 【转】angular Ajax请求
  6. Windows下svn客户端和服务器的安装使用
  7. Android Activity启动模式
  8. 企业架构研究总结(41)——企业架构与建模之ArchiMate的由来和详述(上)
  9. 防止微信浏览器video标签全屏的问题
  10. django使用model创建数据库表使用的字段
  11. Nodejs MSSQL详细解读
  12. java设计师初入职场,如何站稳脚跟
  13. linux下安装nginx与配置
  14. 路飞学城-Python开发集训-第5章
  15. Ubuntu16.04安装MySQL
  16. Maven聚合工程的使用
  17. Public key for ambari-server-2.4.2.0-136.x86_64.rpm is not installed 安装ambari报错总结
  18. 百度地图报错:APP Referer校验失败
  19. Python:windows下scikit-learn 安装和更新
  20. kubeadm快速部署Kubernetes单节点

热门文章

  1. MTK UART串口调试
  2. 1.js 模拟a标签打开新网页
  3. 运用Eclipse的Working Set,界面清爽多了
  4. CV_Assert
  5. ASP.NET Core会议管理平台实战_2、基本概念的理解
  6. python 并发编程之IO 模型
  7. HDU - 2036 改革春风吹满地 叉乘法求多边形面积
  8. [OpenGL]配置GLFW(超详细)
  9. 洛谷 - P1338 - 末日的传说 - 打表
  10. Spring中配置Dbutils