题解 P2704 【[NOI2001]炮兵阵地】

· · 题解

首先此题是一个状压dp，思路非常简单，过程也清晰明了：

1.输入

2.预处理 + 初始化

3.dp

4.找最大并输出

很多巨佬这题都使用了滚动数组，还有人在争论某些题解会爆空间。

但是我太菜了并不会滚动数组怎么办呢？？？

首先上代码

int n, m, mapp[105], cnt = 0, f[105][105][105];

struct point 
{
    int s, num;
}a[105];

什么??

开105就够了？？？

这就涉及到了我们的第二步：预处理

本篇题解就来解析一下之前的题解都没有提到的预处理。

还是先上代码：

cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            mapp[i] = (mapp[i] << 1) + (c == 'P');
        }
    for(int i = 0; i < (1 << m); i++)
    {
        if((i & (i << 1)) || (i & (i << 2)) || (i & (i >> 1)) || (i & (i >> 2))) continue;
        cnt++;
        a[cnt].s = i;
        for(int j = 0; (1 << j) <= i; j++) a[cnt].num += !!(i & (1 << j));
        if((i & mapp[1]) == i) f[1][0][cnt] = a[cnt].num;
    }

枚举每次状态（i）

然后通过左移与右移判断出是否有不符合题目条件的状态并记录下来

这个记录状态的过程，相当于一个离散化，可以大大减小数据数量

通过输出m = 10时的cnt值，我们发现状态最多只会有60个

于是只需要开到65就可以了（为了保险我开了105）

所以是不是不用滚动数组了！！！

预处理在所有状压dp中的运用：

在日常刷题中，我们不能保证每个状压dp题都可以使用滚动数组。

所以，我们要理解这个预处理的过程，然后再也不用担心状压MLE啦！！！

最后附上ac代码：

#include<bits/stdc++.h>

using namespace std;

int n, m, mapp[105], cnt = 0, f[105][105][105];

struct point 
{
    int s, num;
}a[105];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            mapp[i] = (mapp[i] << 1) + (c == 'P');
        }
    for(int i = 0; i < (1 << m); i++)
    {
        if((i & (i << 1)) || (i & (i << 2)) || (i & (i >> 1)) || (i & (i >> 2))) continue;
        cnt++;
        a[cnt].s = i;
        for(int j = 0; (1 << j) <= i; j++) a[cnt].num += !!(i & (1 << j));
        if((i & mapp[1]) == i) f[1][0][cnt] = a[cnt].num;
    }
    cout << cnt << endl; //这个是预处理后的个数
    for(int i = 1; i <= cnt; i++)
        for(int j = 1; j <= cnt; j++)
            if(!(a[i].s & a[j].s) && (mapp[2] & a[j].s) == a[j].s) f[2][i][j] = f[1][0][i] + a[j].num;
    for(int i = 3; i <= n; i++)
        for(int j = 1; j <= cnt; j++)
            if((mapp[i] & a[j].s) == a[j].s) 
                for(int k = 1; k <= cnt; k++)
                    if(!(a[j].s & a[k].s))
                        for(int l = 1; l <= cnt; l++)
                        {
                            if(!(a[k].s & a[l].s) && !(a[j].s & a[l].s)) f[i][k][j] = max(f[i][k][j], f[i - 1][l][k] + a[j].num);
                        }
    int ans = 0;
    for(int i = 1; i <= cnt; i++)
        for(int j = 1; j <= cnt; j++) ans = max(ans, f[n][i][j]);
    printf("%d\n", ans);
    return 0;
}