求助

Star1_3st @ 2019-04-21 17:34:40

#include<bits/stdc++.h>
using namespace std;
struct st
{
    int st[2000],num;
}r[105];
int count(int x)
{
    int c=0;
    while(x)
    {
        c+=x&1;
        x>>=1;
    }

    return c;
}

int n,m,f[105],k[105][105],ans;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char a;
            cin>>a;
            if(a=='P')
                f[i]=(f[i]<<1)+1;
            else 
                f[i]<<=1;
        }

        int num=0;
        for(int j=0;j<(1<<m);j++)
            if(j&(j<<1)||j&(j>>1)||j&(j<<2)||j&(j>>2)||(j&f[i])-j)
                continue;
            else
                r[i].st[++num]=j,r[i].num=num;
    }

    for(int i=1;i<=r[1].num;i++)
        k[1][i]=count(r[1].st[i]);
    for(int i=1;i<=r[2].num;i++)
        for(int j=1;j<=r[1].num;j++)
        {
            if(r[2].st[i]&r[1].st[j])
                continue;
            k[2][i]=k[1][j]+count(r[2].st[i]);
        }

    for(int i=2;i<=n;i++)
        for(int j=1;j<=r[i].num;j++)
            for(int l=1;l<=r[i-2].num;l++)
                for(int o=1;o<=r[i-1].num;o++)
                {
                    if(r[i].st[j]&r[i-1].st[o]||r[i].st[j]&r[i-2].st[l]||r[i-1].st[o]&r[i-2].st[l])
                        continue;
                    k[i][j]=k[i-1][o]+count(r[i].st[j]);
                }

    for(int i=1;i<=r[n].num;i++)
        ans=max(ans,k[n][i]);
    cout<<ans;
    return 0;
}

/*
10 6
HPHPHP
HPHPHH
PHHPPH
HPHPPH
HPHPHP
HHPPHP
PHHPPH
HPPHHH
PHPHHH
PHPHHH

7 4
PHPP
PPPP
PPPP
PPPP
PPPP
PPPP
PPPP

*/

by G我就是菜G @ 2019-04-21 17:39:37

【NOI2001】炮兵阵地（状压DP）

题目描述

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

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

【输入格式】

第一行包含两个由空格分割开的正整数，分别表示 N 和 M ；

接下来的 N 行，每一行含有连续的 M 个字符（ 'P' 或者 ‘H’ ），中间没有空格。按顺序表示地图中每一行的数据。N\le100;M\le10。

【输出格式】

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

【输入样例#1】

5 4

PHPP

PPHH

PPPP

PHPP

PHHP

【输出样例#1】

6

【题解】

本题中，我们读入时需对地形进行处理，我们令 'H' （山地）为 1 ，令 'P' （平原）为 0

这样就能将每一行有一个长为 m 的二进制数来表示，我们用数组 a[i] 表示第 i 行的地形

同理我们将放士兵的位置用 1 表示，不放的位置用 0 表示

这样行放士兵的情况也能用一个长度为 m 的二进制数来表示

我们用 dp[i][j][k] 表示第 i 行状态为 k ，第 i-1 行状态为 j 的方案数

故我们可以推出如下状态转移方程式：

其中 l 为第 i-2 行的状态, j 表示第i-1 行的状态, k 表示第 i 行的状态 Sum[k] 表示 k 在二进制下 1 的个数 状态 j,k,l 分别在第 i-1,i,i-2 行上合法

至于 Sum 数组只需在做前预处理即可

判断该状态是否合法有以下几个注意点：

1. 判断该位置是否为山地，即 !(j\&a[i]==0)（只要有一个地方既是山地又有士兵，结果就为0）
2. 判断该位置前后两格之内是否有其它士兵，即 !(j\&(j<<1)||j\&(j<<2)))（只要向一个方向做移位运算即可，因为移位运算是相对的，即 j\&(j<<1) 等价于 j\&(j>>1)）
3. 判断该位置上面两格之内是否有其他士兵，即 !(j\&k||j\&l||k\&l) （结果为0，就说明上两个状态与此状态冲突）

同时我们发现当前状态之于前面一排的状态有关，我们只需保存前面一排的状态就行了

否则会MLE 0！！！

最后枚举最后两排的情况，取最大值进行输出

【代码】

#include <bits/stdc++.h>
#define Maxn 1025 
using namespace std;
int n,m,a[Maxn],ans[2][Maxn][Maxn],Ans,Sum[Maxn];
char c;
int getsum(int x)
{
    int sum=0;
    while (x) {
        if (x&1) sum++;
        x>>=1;
    }
    return sum;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            cin>>c,a[i]<<=1,a[i]+=(c=='H'?1:0);
    for (int i=0;i<(1<<m);i++)
        Sum[i]=getsum(i);
    for (int i=0;i<(1<<m);i++)
        if (!(i&a[1]||i&(i<<1)||i&(i<<2)))
            ans[1][0][i]=Sum[i];
    for (int i=0;i<(1<<m);i++)
        for (int j=0;j<(1<<m);j++)
            if (!(i&a[1]||j&a[2]||i&j||i&(i<<1)||i&(i<<2)||j&(j<<1)||j&(j<<2)))
                ans[0][i][j]=Sum[i]+Sum[j];
    for (int i=3;i<=n;i++)
        for (int j=0;j<(1<<m);j++)
        {
            if (j&a[i-1]||j&(j<<1)||j&(j<<2)) continue;
            for (int k=0;k<(1<<m);k++)
            {
                if (k&a[i]||k&j||k&(k<<1)||k&(k<<2)) continue;
                for (int l=0;l<(1<<m);l++)
                {
                    if (l&a[i-2]||l&j||l&k||l&(l<<1)||l&(l<<2)) continue;
                    ans[i%2][j][k]=max(ans[i%2][j][k],ans[(i-1)%2][l][j]+Sum[k]);
                }
            }
        }
    for (int i=0;i<(1<<m);i++)
        for (int j=0;j<(1<<m);j++)
            Ans=max(Ans,ans[n%2][i][j]);
    printf("%d\n",Ans);
    return 0;
}

by Agakiss @ 2019-04-21 18:59:01

%%%