这个题目是个挺难表示的状态DP,因为不但要考虑上下还要考虑左右,在DP里面就没有什么下了咯,但也至少除了考虑左右还要考虑上

所以先枚举出在同一行满足条件的状态 即 某状态 若 s&(s<<1) 或者(s&(s<<2)) 则说明同一行的炮塔在射击范围内,要去掉。

然后就是考虑不同行的了,只要上一行和上上行的状态不冲突即可

于是就有了如下状态

dp[i][j][k]代表第i行状态为k,上一行的状态为j时的最大值。

于是它的子状态就是 dp[i-1][w][j]代表上一行的状态为j 上上行的状态为w的最大值。

于是 dp[i][j][k]=max(dp[i][j][k],dp[i-1][w][j]+calc[k]) (calc代表某个状态中1的个数 即炮塔的数目)。

需要枚举四层循环 中间通过状态的对比来去掉一些没用的状态。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 11
using namespace std;
int dp[105][<<N-][<<N-];
int A[105],m,n,calc[<<N],num,state[<<N];
void init()
{
num=;
for (int i=;i<(<<m);i++)
{
int tmp=;
if (i&(i<<) || i&(i<<)) continue; //左右有冲突 跳过。
state[num]=i;
for (int j=;j<m;j++)
{
if ((<<j)&i)
tmp++;
}
calc[num++]=tmp; //算出某个状态中的含1的个数
}
}
bool fit(int a,int b)//判断上下某个状态是否冲突
{
if (a&b) return ;
return ;
}
void DP()
{
int ans=;
for (int i=;i<num;i++) //先预处理第一行的情况
{
if (!fit(state[i],A[]))
continue;
dp[][][i]=calc[i];
ans=max(ans,dp[][][i]);
}
for (int i=;i<=n;i++)
{
for (int k=;k<num;k++) //这里的是先枚举k还是j 没什么大关系,两个状态彼此独立。
{
for (int j=;j<num;j++)
{
if (!fit(state[j],state[k])|| !fit(state[k],A[i]) || !fit(state[j],A[i-]))//有冲突就直接跳过
continue;
for (int w=;w<num;w++)
{
if (!fit(state[j],state[w])|| !fit(state[k],state[w]))
continue;
if (!fit(state[w],A[i-])) continue;
dp[i][j][k]=max(dp[i][j][k],dp[i-][w][j]+calc[k]);
ans=max(ans,dp[i][j][k]);
}
}
}
}
printf("%d\n",ans);
}
int main()
{
char c; while (scanf("%d%d",&n,&m)!=EOF)
{
init();
memset(dp,,sizeof dp);
for (int i=;i<=n;i++)
{
getchar();
A[i]=;
for (int j=;j<m;j++)
{
c=getchar();
if (c=='H')
A[i]+=<<j; //这里故意把H设置为1,是为了正好用上面的fit函数,如果有状态把炮塔建在H上,就是不可取的状态。
// cout<<c;
}
// cout<<endl;
}
DP(); }
return ;
}

最新文章

  1. 使用Red Gate Sql Data Compare 数据库同步工具进行SQL Server的两个数据库的数据比较、同步
  2. 【转载】JS中bind方法与函数柯里化
  3. ThinkPad指纹验证在win7无法使用的解决方法
  4. ASP.NET - 使用MqSql数据库
  5. USB的前世今生
  6. An explicit value for the identity column in table can only be specified when a column list is used and IDENTITY_INSERT is ON
  7. JavaScript 组数去重demo
  8. 查询正在运行的请求及其后台对应SQL
  9. 移动端UL列表无法平滑向下滚动问题
  10. Gitblit版本服务器环境部署记录
  11. ppt转成图片等其它对象
  12. python URLError,HTTPError 的异常处理
  13. centOS 安装 Webmin
  14. ssh登录时在参数中加入密码的解决方案
  15. POJ-1189 钉子和小球(动态规划)
  16. JAX-RS(REST Web Services)2.0 can not be installed: One or more constraints have not been satisfied
  17. [转] ELK 之 Logstash
  18. SharePoint Managed Metadata 使用总结
  19. Codeforces Round 253 (Div. 2)
  20. 学习笔记_TCP编程,服务端

热门文章

  1. python scipy样条插值函数大全(interpolate里interpld函数)
  2. 吴裕雄 Bootstrap 前端框架开发——Bootstrap 字体图标(Glyphicons):glyphicon glyphicon-cog
  3. SYSTEMTIME 获取日期之差
  4. 《Java面试全解析》1000道面试题大全详解(转)
  5. 【LeetCode】反转字符串
  6. [洛谷Luogu]P1803 线段覆盖问题
  7. 文献阅读报告 - Social Ways: Learning Multi-Modal Distributions of Pedestrian Trajectories with GANs
  8. 第三节MapStruct翻译--Defining a mapper
  9. c# 多张图片合成一张图片
  10. java开发 中台