[POJ1185][NOI2001]炮兵阵地 状压DP
2024-08-30 01:04:42
题目链接: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 ;
}
最新文章
- W7无法更新
- CSS3之让背景图片全部显示
- Hive与数据库的异同
- Groovy读取properties及txt
- 【转】angular Ajax请求
- Windows下svn客户端和服务器的安装使用
- Android Activity启动模式
- 企业架构研究总结(41)——企业架构与建模之ArchiMate的由来和详述(上)
- 防止微信浏览器video标签全屏的问题
- django使用model创建数据库表使用的字段
- Nodejs MSSQL详细解读
- java设计师初入职场,如何站稳脚跟
- linux下安装nginx与配置
- 路飞学城-Python开发集训-第5章
- Ubuntu16.04安装MySQL
- Maven聚合工程的使用
- Public key for ambari-server-2.4.2.0-136.x86_64.rpm is not installed 安装ambari报错总结
- 百度地图报错:APP Referer校验失败
- Python:windows下scikit-learn 安装和更新
- kubeadm快速部署Kubernetes单节点