poj 1185 炮兵阵地 （状态压缩dp）
【摘要】
题目链接
如果你是刚刚开始做状态压缩dp，我建议你先看看 poj 3254 Corn Fields 这是一道比这一题更简单，更容易入门的题目。 还有在代码中我用了一个很巧妙的方法求一个数二进制数中1的个数 具体请看我博客中 x& (x...
如果你是刚刚开始做状态压缩dp，我建议你先看看 poj 3254 Corn Fields 这是一道比这一题更简单，更容易入门的题目。
还有在代码中我用了一个很巧妙的方法求一个数二进制数中1的个数 具体请看我博客中 x& (x - 1)==0 这篇文章 链接 。
还有一点，不同于poj 3254的地方，我们不能直接枚举所有的状态。我在getresult()中用到了四重循环，直接枚举的时间复杂度是2^40，并且dp那个数组也是开不下到，不过对于这道题还是有方法的。枚举一行所有的状态，行合法（没有两个1相隔少于两个）的状态总共有61中，我们只需要枚举所有合法状态即可，循环次数最多是61^4。
代码
-
#include <stdio.h>
-
#include <string.h>
-
#include <algorithm>
-
using namespace std;
-
-
const int maxn = 62; //每行合法的状态总共有61种
-
int dp[102][maxn][maxn]; //因为状态是与前两行有关，所以用到三维数组
-
int sta[102]; //每行不能放置的点
-
int cnt[maxn]; //状态中1的数目，也就是炮的数目
-
int allsta[maxn]; //所有可能的状态
-
int n, m;
-
int num; //满足条件的状态数
-
-
bool judgeself(int x) //判断x状态是不是有会相互攻击的状态，也就是有没有两个1相隔少于两个0
-
{
-
if (x&(x<<1) || x&(x<<2))
-
return false;
-
return true;
-
}
-
-
int count(int x) //用很巧妙的计算出x二进制中1的个数
-
{
-
int s = 0;
-
while (x)
-
{
-
s++;
-
x = x&(x-1);
-
}
-
return s;
-
}
-
-
void search(int x)
-
{ //这个函数相当于把对状态进行了离散化，去掉了每行所有不合法的状态
-
int t = 1<<x;
-
num = 0;
-
for (int i = 0; i < t; i++)
-
{
-
if (judgeself(i))
-
{
-
allsta[num] = i;
-
cnt[num] = count(i);
-
num++;
-
}
-
}
-
}
-
-
bool fit(int x, int y)
-
{
-
if(x&y)
-
return false;
-
return true;
-
}
-
-
void getresult()
-
{
-
memset(dp, 0, sizeof(dp));
-
for (int i = 0; i < num; i++) //因为计算每行的时候需要用到前两行的状态，需要对第一行特殊处理
-
{
-
for (int j = 0; j < num; j++)
-
{
-
if (fit(sta[1], allsta[i]) && fit(allsta[i], allsta[j]))
-
dp[1][j][i] = cnt[i];
-
}
-
}
-
for (int i = 2; i <= n; i++)
-
{
-
for (int j = 0; j < num; j++)
-
{
-
if (!fit(sta[i], allsta[j]))
-
continue;
-
for (int k = 0; k < num; k++)
-
{
-
if (!fit(allsta[j], allsta[k])) // 判断是否与前一行冲突
-
continue;
-
for (int l = 0; l < num; l++)
-
{
-
if (!fit(allsta[j], allsta[l])) //不光要判断是否与前一行冲突，要判断第前两行
-
continue;
-
dp[i][k][j] = max(dp[i][k][j], dp[i-1][l][k]+cnt[j]);
-
}
-
}
-
}
-
}
-
int ans = 0;
-
for (int i = 0; i < num; i++)
-
{
-
for (int j = 0; j < num; j++)
-
{
-
if (!fit(allsta[i], allsta[j]))
-
continue;
-
ans = max(ans, dp[n][i][j]); //求出最后一行最大的结果
-
}
-
}
-
printf("%d\n", ans);
-
}
-
-
int main()
-
{
-
while (scanf("%d %d", &n, &m) != EOF)
-
{
-
memset(sta, 0, sizeof(sta));
-
search(m);
-
for (int i = 1; i <= n; i++)
-
{
-
getchar();
-
for (int j = 1; j <= m; j++)
-
{
-
char t;
-
scanf("%c", &t);
-
if (t == 'H')
-
sta[i] += (1<<(m-j)); //标记一行中不能安放炮兵的状态
-
}
-
}
-
getresult();
-
}
-
return 0;
-
}
文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。
原文链接：xindoo.blog.csdn.net/article/details/8902190
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）