P2704

Aryper · 2021-11-11 16:19:13 · 个人记录

[NOI2001] 炮兵阵地

一开始也是使用三进制写的，但实现的太屑了，所以挂掉了。

我们定义每一位，如果状态的第 i 位为 0 表示什么都没有，1 表示有中间的余波，2 表示有炮。

那么我们主要看上一行，同时根据上一行确定该行的基础状态。

枚举上一行可能的情况，判断是否存在。

在存在的状态中得到当前行基础状态，在基础状态上继续确定是否有可放炮的位置，具体实现为搜索。中间再进行 DP。能放炮的充要条件是上一行无余波，这一行基础状态为 0，并且这个格没有山。

这里的 dfs 实现方式比较非常规但是非常简洁美观。

最后时间复杂度 O(nm3^m)。

相比于大部分两行状态的题解（理论时间复杂度是无法通过的），这个方法应该是最为优美的了。

注意一些三进制的处理技巧，可以应用于更多的状压。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;

const ll N=1e2,M=10,I=6e4;

ll n,m,cur,ans;

ll a[N+5][M+5],f[2][I+5],tmp[M+5],nxt[M+5],pre[M+5],ter[M+5];
// Ternary & Decimal
char s[M+5];

ll Ter_to_Dec(ll *arr) {
    ll res=0;
    for(ll i=1;i<=m;i++) res+=ter[i-1]*arr[i];
    return res;
}

void Dec_to_Ter(ll x,ll *arr) {
    for(ll i=1;i<=m;i++) {
        arr[i]=x%3;x/=3;
    }
}

void dfs(ll x,ll cnt) {
    ll S=Ter_to_Dec(nxt);
    f[cur][S]=max(f[cur][S],cnt);
    ans=max(ans,cnt);
    for(;x<=m;x++) {
        if(!pre[x]&&!nxt[x]&&!tmp[x]) {
            nxt[x]=2;dfs(x+3,cnt+1);nxt[x]=0;
        }
    }
}

void init() {
    ter[0]=1;
    for(ll i=1;i<=10;i++) ter[i]=(ter[i-1]<<1)+ter[i-1];
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    init();

    n=read();m=read();

    for(ll i=1;i<=n;i++) {
        scanf("%s",s+1);
        for(ll j=1;j<=m;j++) {
            if(s[j]=='H') a[i][j]=1;
        }
    }

    memset(f,-1,sizeof(f));
    f[1][0]=0;

    for(ll i=1;i<=n;i++) {
        memset(f[cur],-1,sizeof(f[cur]));
        for(ll j=0;j<ter[m];j++)
        if(f[cur^1][j]!=-1) {
            Dec_to_Ter(j,pre);
            for(ll k=1;k<=m;k++) {
                tmp[k]=a[i][k];nxt[k]=max(0ll,pre[k]-1);
            }
            dfs(1,f[cur^1][j]);
        }
        cur^=1;
    }

    write(ans);

    return 0;
}