【POJ1185】炮兵阵地

2024-08-31 17:08
文章标签 炮兵阵地 poj1185

本文主要是介绍【POJ1185】炮兵阵地,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

炮兵阵地
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 20433 Accepted: 7917

Description

司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示:

如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的炮兵部队。

Input

第一行包含两个由空格分割开的正整数,分别表示N和M;
接下来的N行,每一行含有连续的M个字符('P'或者'H'),中间没有空格。按顺序表示地图中每一行的数据。N <= 100;M <= 10。

Output

仅一行,包含一个整数K,表示最多能摆放的炮兵部队的数量。

Sample Input

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

Sample Output

6

Source

Noi 01

1.调了这么久,结果发现是把char mp[][] 写成了int mp[][];  233333

2. 有地图匹配的话,用地图的反 & 枚举值。如果((地图的反 & 枚举值) == 0) 则是可以的。

3.如果是有冲突的话,那么平移使得冲突发生。如果真的有冲突的话,那么不可以。


#include <cstring>
#include <iostream>
#include <stdio.h>
using namespace std;

int N,M;
char mp[110][60];
int cur[110];
int state[110];
int dp[110][60][60];
int num[110];
int stanums;
int upp;

bool ok(int x)
{
    if(x & (x << 1)) return false;
    if(x & (x << 2)) return false;
    return true;
}

int calbits(int x)
{
   int cnt = 0;
   while(x > 0)
   {
     cnt ++;
     x &= (x-1);
   }
   return cnt;
}

bool fit(int x,int cur)
{
    if(x & cur) return false;
    return true;
}

int main()
{
    while(scanf("%d%d",&N,&M) != EOF)
    {
        memset(mp,0,sizeof(mp));
        memset(cur,0,sizeof(cur));
        memset(dp,-1,sizeof(dp));
        stanums = 1;
        for(int i=1;i<=N;i++)
        {
            scanf("%s",mp[i]+1);
        }

        for(int i=1;i<=N;i++)
            for(int j=1;j<=M;j++)
        {
            if(mp[i][j] == 'H')
            {
                cur[i] += (1 << (j-1));
            }
        }

        upp = (1 << M);
        for(int i=0;i<upp;i++)
        {

            if(ok(i))
            {
                num[stanums] = calbits(i);
                state[stanums++] = i;
            }

        }

        for(int i=1;i<stanums;i++)
        {
            if(fit(state[i],cur[1]))
            {
                dp[1][1][i]= num[i];
            }
        }


        for(int i=2;i<=N;i++)
        {
            for(int j=1;j<stanums;j++)
            {
            
                if(!fit(state[j],cur[i])) continue;
                for(int k=1;k<stanums;k++)
                {
                    if(state[j] & state[k]) continue;
                    for(int z=1;z<stanums;z++)
                    {
                        if(state[j] & state[z]) continue;
                        if(dp[i-1][z][k] == -1) continue;

                
                        dp[i][k][j] = max(dp[i][k][j],dp[i-1][z][k] + num[j]);
                    
                    }
                 }
            }
        }

        int ans = -1;
        for(int i=1;i<stanums;i++)
            for(int j=1;j<stanums;j++)
        {
            ans = max(ans,dp[N][i][j]);
        }
        printf("%d\n",ans);
    }

 
}




这篇关于【POJ1185】炮兵阵地的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1124486

相关文章

poj1185--炮兵阵地(状压dp)

炮兵阵地 Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 20169 Accepted: 7805 Description 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地

poj 1185 炮兵阵地(动态规划:状压DP)

用二进制数表示一行的状态 预处理记录满足条件的状态对应十进制数 因为当前行仅与上两行有关,所以状态转移方程为: dp[i][k][t] = max(dp[i][k][t], dp[i-1][j][k]+num[t]) num[t]表示状态t对应的炮台数 dp[i][k][t]表示第i行状态为t,第i-1行状态为k时对应的最大值 代码如下: #include <cstdio>#i

NYOJ 81 炮兵阵地

炮兵阵地 时间限制: 2000 ms  |  内存限制: 65535 KB 难度: 6 描述 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色

poj -- 1185 炮兵阵地

题解:二进制压缩,枚举每行存在的状态,判断与前一行的状态的关系,找出最大值 dp[i][j][k] = max(dp[i][j][k] , dp[i-1][k][[l] + p[j]) 表示第i行第j个状态,i-1行的第k个状态炮兵的最大数量 #include<stdio.h>#include<string.h>#include<iostream>#include<algorithm

poj1185 AcWing 292. 炮兵阵地(状压dp)

司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成,地图的每一格可能是山地(用”H” 表示),也可能是平原(用”P”表示),如下图。 在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: 1185_1.jpg 如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻

POJ 1185 - 炮兵阵地

Description 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: 如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表

炮兵阵地 POJ - 1185

点击打开链接 第i行只和第i-1行 第i-2行有关 显然要DP 发现列数很小 考虑状态压缩 但若使dp[i][j][k]代表在第i行 第i行取j状态 第i-1行取k状态 那复杂度就是n*(2^m)*(2^m)*(2^m) 这里最巧妙的是 对于某一行 它所有状态中 满足炮兵两两不交叉的状态非常少 因为这相当于要求二进制位上相邻1至少相隔两位 这样就把m变的很小 最后注意一下细节     #

poj1185状态压缩DP

炮兵阵地 Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 19991 Accepted: 7737 Description 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地形上最多

(POJ 1185)炮兵阵地 状压DP经典题目

炮兵阵地 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用”H” 表示),也可能是平原(用”P”表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: 如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区

题解 P2704 【炮兵阵地】

这道题和P1879 [USACO06NOV]玉米田Corn Fields有类似的地方,但这道题可以看为那道题的升级版,所以我建议没做过玉米田的可以先做一下玉米田和P1896 [SCOI2005]互不侵犯King。 1. 解此题的关键在于要知道第i行的状态是由前两行的状态决定的,所以要预处理出第一行和第二行的所有状态,然后从第三行(因为第一二行已处理)开始枚举,同时枚举第当前行的前一行和上上行。