2018.09.08 poj1185 炮兵阵地(状压dp)
2024-09-14 10:22:09
传送门
状压dp经典题。
我们把每一行的状态压成01串。
预处理出每一行可能出现的状态,然后转移每个被压缩的状态的1的个数就行了。
注意当前行转移要考虑前两行的状态。
还要注意只有一行的情况。
代码:
#include<iostream>
#include<cctype>
#include<cstdio>
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int sta[105][70],tot[105],n,m,f[105][70][70],cal[105][70];
inline int calc(int x){
int ret=0;
while(x)x-=x&-x,++ret;
return ret;
}
int main(){
n=read(),m=read(),tot[0]=1;
for(int i=1;i<=n;++i){
char s[15];
int x=0;
scanf("%s",s);
for(int j=0;j<m;++j)if(s[j]=='H')x|=1<<j;
for(int j=0;j<(1<<m);++j){
if((j&(j<<1))||(j&(j<<2))||(j&x))continue;
sta[i][++tot[i]]=j,cal[i][tot[i]]=calc(j);
}
}
for(int i=1;i<=tot[1];++i)f[1][i][1]=cal[1][i];
for(int i=1;i<=tot[2];++i)
for(int j=1;j<=tot[1];++j){
if(sta[2][i]&sta[1][j])continue;
f[2][i][j]=max(f[2][i][j],f[1][j][1]+cal[2][i]);
}
for(int i=3;i<=n;++i){
for(int j=1;j<=tot[i];++j)
for(int k=1;k<=tot[i-1];++k){
if(sta[i][j]&sta[i-1][k])continue;
for(int l=1;l<=tot[i-2];++l){
if((sta[i][j]&sta[i-2][l])||(sta[i-1][k]&sta[i-2][l]))continue;
f[i][j][k]=max(f[i][j][k],f[i-1][k][l]+cal[i][j]);
}
}
}
int ans=0;
for(int i=1;i<=tot[n];++i)
for(int j=1;j<=tot[n-1];++j){
if(sta[n][i]&sta[n-1][j])continue;
ans=max(ans,f[n][i][j]);
}
cout<<ans;
return 0;
}
最新文章
- softwareTesting_work1
- unity3d 日志捕捉
- Android开发——实现固定在ScrollView顶部的View,类似于新浪微博的评论列表的顶部
- WebSocket 实战
- Ember.js - About
- FileStream:The process cannot access the file because it is being used by another process
- jquery如何判断元素是否被点击_百度知道
- 使用node-inspector调试nodejs程序<;nodejs>;
- Google word/sheets 常见的使用:
- shell脚本编写某一文件夹内拷贝某一段文件(有则跳过没有则拷贝)
- [译]ASP.NET Core Web API 中使用Oracle数据库和Dapper看这篇就够了
- Android内存优化之内存缓存
- macOS Sierra 10.12.6 odoo 10.0 开发环境配置
- cut语法
- Android 让图片等比例缩放的三种方法
- 什么是SASS
- TEST DESIGN TECHNIQUES: AN OVERVIEW
- 内部排序->;选择排序->;树形选择排序
- windows类型
- kali64位 安装 adb