题解：P10865 [HBCPC2024] Genshin Impact Startup Forbidden III

一个位置最多只有 $3$ 条鱼，而所有有鱼的格子不超过 $10$，所以我们可以写一个 $4$ 进制的状态压缩。设 $dp_s$ 表示 $k$ 个有鱼的格子中受到炸弹影响后的状态为 $s$ 时所需要的最小的炸弹的数量。

同时，由于一个炸弹只能影响到五个格子，所以我们可以预处理出不超过 $50$ 个可能会放炸弹的位置。当状态为 $s$ 时，在某处放入一个炸弹，我们可以将 $s$ 每一位分离后，修改炸弹影响到的那些位置，然后再重新获得 $s’$。因此可以列出转移方程 $dp_{s’} = \min (dp_{s’},dp_s + 1)$。

最后的时间复杂度约为 $O(4^k \times k^2)$，可以通过此题。代码如下：

#include <bits/stdc++.h>
#define init(x) memset (x,INF,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 2e6 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,m,k,p,tot,v[15],dp[MAX],sx[] = {0,1,-1,0,0},sy[] = {0,0,0,1,-1};
vector <int> tmp;
set <pair <int,int> > loc;
map <pair <int,int>,int> id;
int main ()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    n = read ();m = read ();k = read ();
    for (int i = 0;i < k;++i)
    {
        int x = read (),y = read ();v[i] = read ();
        id[{x,y}] = i;//用 map 记录下对应的位置
        for (int j = 0;j < 5;++j)
        {
            int xx = x + sx[j],yy = y + sy[j];
            if (1 <= xx && xx <= n && 1 <= yy && yy <= m) loc.insert ({xx,yy});//预处理出炸弹可能放置的位置，用 set 去重
        }
        tot = tot * 4 + v[i];//处理出对应的四进制数
    }
    init (dp);dp[0] = 0;
    for (int i = 0;i <= (1 << (2 * k));++i)
    {
        if (dp[i] == INF) continue;
        for (auto nxt : loc)
        {
            int x = nxt.first,y = nxt.second;
            p = i;tmp.clear ();
            for (int j = 1;j <= k;++j) tmp.push_back (p % 4),p /= 4;//逐位分离
            for (int j = 0;j < 5;++j)
            {
                int xx = x + sx[j],yy = y + sy[j];
                if (id.find ({xx,yy}) == id.end ()) continue;//不需要放置炸弹
                int o = id[{xx,yy}];
                tmp[k - o - 1] = min (v[o],tmp[k - o - 1] + 1);//炸弹最多不超过格子中鱼的数量  注意下标
            }
            p = 0;
            for (int i = tmp.size () - 1;~i;--i) p = p * 4 + tmp[i];//重新计算出新的状态
            dp[p] = min (dp[p],dp[i] + 1); 
        }
    }
    printf ("%d\n",dp[tot]);
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}