M_sea

洛谷2704 [NOI2001]炮兵阵地
Luogu算法考虑状压DP。我们可以先预处理出所有行内合法状态,然后处理前两行的边界,最后DP即可。注意,DP时要...
扫描右侧二维码阅读全文
06
2018/09

洛谷2704 [NOI2001]炮兵阵地

Luogu

算法

考虑状压DP。

我们可以先预处理出所有行内合法状态,然后处理前两行的边界,最后DP即可。

注意,DP时要枚举三行的状态。

最后答案枚举两行,取最大即可。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int S[1<<10],sum[1<<10],tot=0;
int f[3][1<<10][1<<10];
int cv[1<<10];

int main() {
    int n=read(),m=read();
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=m;j++) {
            char c;
            do c=getchar(); while (c!='P'&&c!='H');
            if (c=='H') cv[i]|=(1<<j-1);
        }
    for (re int i=0;i<1<<m;i++) {
        if ((i&(i<<1))||(i&(i<<2))) continue;
        S[++tot]=i; int j=i;
        while (j) j-=j&-j,sum[tot]++;
        if (!(i&cv[1])) f[1][tot][0]=sum[tot];
    }
    for (re int i=1;i<=tot;i++)
        for (re int j=1;j<=tot;j++) {
            if ((S[i]&S[j])||(S[j]&cv[2])) continue;
            f[2][j][i]=f[1][i][0]+sum[j];
        }
    for (re int i=3;i<=n;i++) {
        int now=i%3,pre=(now+5)%3;
        memset(f[now],0,sizeof(f[now]));
        for (re int j=1;j<=tot;j++) {
            if (S[j]&cv[i]) continue;
            for (re int k=1;k<=tot;k++) {
                if (S[j]&S[k]) continue;
                for (re int p=1;p<=tot;p++) {
                    if ((S[j]&S[p])||(S[k]&S[p])) continue;
                    f[now][j][k]=max(f[now][j][k],f[pre][k][p]+sum[j]);
                }
            }
        }
    }
    int ans=0;
    for (re int i=1;i<=tot;i++)
        for (re int j=1;j<=tot;j++)
            ans=max(ans,f[n%3][i][j]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 12 月 01 日 08 : 34 PM

发表评论