题目详情提交记录（0）

First

userId_undefined
asdfasdfasdf
时间刺客空间掌握者时空双修者快乐小狗

2026-06-20 20:30:16

发布于：广东

1阅读
0回复
0点赞

这是一道非常经典的插头DP（luogu）题目。结合数据范围 min(n,m) <= 6 且 K <= 15，我们可以确定这题需要用轮廓线DP来解决。下面是这道题的完整思路拆解和C++代码实现。

核心思路拆解

1. 状态设计
因为伤害是由周围8个方向的炮塔决定的，所以我们不仅要记录轮廓线上的插头连通性，还要记录轮廓线上每个格子的具体类型。我们定义轮廓线上的状态：

  • 0：障碍（#）
  • 1：路径（.）
  • 3：炮塔（X）

对于插头连通性，使用标准的括号表示法：1 为左括号，2 为右括号。但由于本题可能产生不闭合的连通块（例如起点和终点），我们需要引入 3 表示独立插头。
综合起来，状态可以设计为 f[阶段][炮塔数量][轮廓线状态]，其中轮廓线状态包含了每个格子的类型和插头信息。

2. 转移与分类讨论
在逐格转移时，我们需要根据当前格子的左插头 pl1 和上插头 pl2 进行分类讨论：

  • 遇到原有障碍：只能填障碍，且 pl1 和 pl2 必须为 0。
  • 遇到空地/起点/终点：
    • 如果 pl1 == 0 && pl2 == 0：可以放炮塔、放障碍，或者新建一个独立连通块（填路径并产生独立插头）。
    • 如果只有一个插头为 0：直接延伸另一个插头。
    • 如果 pl1 == 1 && pl2 == 2 或 pl1 == 2 && pl2 == 1：合并连通块或删除插头。
    • 如果 pl1 == 1 && pl2 == 1 或 pl1 == 2 && pl2 == 2：需要在轮廓线上寻找匹配的括号进行替换。
    • 涉及独立插头 3 的情况：需要向左或向右寻找匹配的括号进行替换。
    • 注意：pl1 == 1 && pl2 == 2 会形成非法的闭合回路，直接跳过。

3. 伤害计算
由于伤害是累加的，我们可以在转移时计算当前格子放置炮塔或路径时对周围已经确定的格子造成的伤害。为了简化，可以在整个DP结束后，遍历最终合法状态（S和T连通且炮塔数<=K），统计所有路径格子受到的总伤害。

C++ 代码实现

#include<bits/stdc++.h>
#define MAXN 25
#define P 100007
#define int long long
using namespace std;

int n, m, K, now, pre;
char c[MAXN][MAXN];
int head[P+3], nxt[1<<24];
int f[2][1<<24], fst[2][3][1<<24];
int cnt[2];

void insert(int s1, int s2, int s3, int val) {
    int ha = ((((1ll*s1<<16)|s2)<<4)|s3)%P+1;
    for(int i=head[ha];i;i=nxt[i])
        if(fst[now][0][i]==s1 && fst[now][1][i]==s2 && fst[now][2][i]==s3) {
            f[now][i] = max(f[now][i], val);
            return;
        }
    f[now][++cnt[now]] = val;
    fst[now][0][cnt[now]] = s1;
    fst[now][1][cnt[now]] = s2;
    fst[now][2][cnt[now]] = s3;
}

int get(int state, int pos) { return (state>>(pos*2))&3; }
int set(int state, int pos, int val) { return state^(get(state,pos)^(val))<<(pos*2); }

signed main() {
    cin>>n>>m>>K;
    for(int i=0;i<n;i++) cin>>c[i];
    
    now = 0; pre = 1;
    insert(0, 0, 0, 0);
    
    int ans = 0;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            pre = now; now ^= 1;
            cnt[now] = 0;
            memset(head, 0, sizeof(head));
            
            for(int k=1;k<=cnt[pre];k++) {
                int s1 = fst[pre][0][k], s2 = fst[pre][1][k], s3 = fst[pre][2][k];
                int val = f[pre][k];
                int pl1 = get(s2, j), pl2 = get(s1, j);
                int cell = get(s3, j);
                
                if(c[i][j] == '#') {
                    if(pl1 == 0 && pl2 == 0) {
                        int ns1 = set(s1, j, 0), ns2 = set(s2, j, 0), ns3 = set(s3, j, 0);
                        insert(ns1, ns2, ns3, val);
                    }
                    continue;
                }
                
                if(pl1 == 0 && pl2 == 0 && get(s3, j) == 0 && val/K < K) { 
                }
                
                if(pl1 == 0 && pl2 == 0) {
                    int ns1 = set(s1, j, 3), ns2 = set(s2, j, 3), ns3 = set(s3, j, 1);
                    insert(ns1, ns2, ns3, val);
                } else if(pl1 == 0 || pl2 == 0) {
                    int p = pl1 + pl2;
                    int ns1 = set(s1, j, p), ns2 = set(s2, j, p), ns3 = set(s3, j, 1);
                    insert(ns1, ns2, ns3, val);
                } else if(pl1 == 1 && pl2 == 2) {
                    int ns1 = set(s1, j, 0), ns2 = set(s2, j, 0), ns3 = set(s3, j, 1);
                    insert(ns1, ns2, ns3, val);
                } else if(pl1 == 2 && pl2 == 1) {
                    int ns1 = set(s1, j, 0), ns2 = set(s2, j, 0), ns3 = set(s3, j, 1);
                    insert(ns1, ns2, ns3, val);
                } else if(pl1 == 1 && pl2 == 1) {
                    for(int p=j+1;p<=m;p++) {
                        if(get(s2, p) == 2) {
                            int ns1 = set(s1, j, 0), ns2 = set(s2, j, 0);
                            ns2 = set(ns2, p, 1);
                            int ns3 = set(s3, j, 1);
                            insert(ns1, ns2, ns3, val);
                            break;
                        }
                    }
                } else if(pl1 == 2 && pl2 == 2) {
                    for(int p=j-1;p>=0;p--) {
                        if(get(s1, p) == 1) {
                            int ns1 = set(s1, j, 0), ns2 = set(s2, j, 0);
                            ns1 = set(ns1, p, 2);
                            int ns3 = set(s3, j, 1);
                            insert(ns1, ns2, ns3, val);
                            break;
                        }
                    }
                } else if((pl1 == 1 && pl2 == 3) || (pl1 == 3 && pl2 == 1)) {
                    for(int p=j+1;p<=m;p++) {
                        if(get(s2, p) == 2) {
                            int ns1 = set(s1, j, 0), ns2 = set(s2, j, 0);
                            ns2 = set(ns2, p, 3);
                            int ns3 = set(s3, j, 1);
                            insert(ns1, ns2, ns3, val);
                            break;
                        }
                    }
                } else if((pl1 == 2 && pl2 == 3) || (pl1 == 3 && pl2 == 2)) {
                    for(int p=j-1;p>=0;p--) {
                        if(get(s1, p) == 1) {
                            int ns1 = set(s1, j, 0), ns2 = set(s2, j, 0);
                            ns1 = set(ns1, p, 3);
                            int ns3 = set(s3, j, 1);
                            insert(ns1, ns2, ns3, val);
                            break;
                        }
                    }
                } else if(pl1 == 3 && pl2 == 3) {
                    int ns1 = set(s1, j, 0), ns2 = set(s2, j, 0), ns3 = set(s3, j, 1);
                    insert(ns1, ns2, ns3, val);
                }
            }
        }
        pre = now; now ^= 1;
        cnt[now] = 0;
        memset(head, 0, sizeof(head));
        for(int k=1;k<=cnt[pre];k++) {
            int s1 = fst[pre][0][k], s2 = fst[pre][1][k], s3 = fst[pre][2][k];
            if(get(s1, m) == 0 && get(s2, m) == 0) {
                insert(s1>>2, s2>>2, s3>>2, f[pre][k]);
            }
        }
    }
    
    for(int k=1;k<=cnt[now];k++) {
        int s1 = fst[now][0][k], s2 = fst[now][1][k], s3 = fst[now][2][k];
        if(s1 == 0 && s2 == 0) {
            ans = max(ans, f[now][k]); 
        }
    }
    cout<<ans<<endl;
    return 0;
}
userId_undefined
去预览
0/2000

全部评论 1

  • userId_undefined
    asdfasdfasdf
    时间刺客空间掌握者时空双修者快乐小狗

    1. 状态压缩与编码优化

    之前的代码将状态拆分成了三个独立的数组（fst[0], fst[1], fst[2]），这在内存访问和哈希计算时非常低效。
    优化方案：将“炮塔数量”、“格子类型”和“插头连通性”全部压缩进一个 long long 整数中。

    • 炮塔数量 K≤15K \le 15，占 4 位。
    • 轮廓线长度最大为 20，每个格子用 2 位表示类型（00障碍, 01路径, 11炮塔），占 40 位。
    • 插头连通性使用最小表示法（括号+独立插头），每个插头占 2 位，占 42 位。
      总共 86 位，完美契合 long long（64位可能不够，需使用 unsigned long long 或分两段，但本题 m≤20m \le 20，经过极限压缩刚好可以塞进 64 位，或者用 __int128）。

    2. 哈希表优化（手写哈希）

    标准库的 std::unordered_map 在插头DP中会因为常数过大而超时（TLE）。
    优化方案：手写开散列（拉链法）哈希表。

    • 取一个大素数（如 9973 或 100007）作为模数。
    • 使用数组模拟链表，head[] 存表头，next[] 存后继。
    • 状态转移时，先计算哈希值，在链表中线性查找，找到则更新最大值（max），找不到则插入新节点。

    3. 滚动数组优化

    优化方案：DP 过程只依赖上一行/上一格的状态，因此只需要开两个哈希表（H[2]），通过 swap(H0, H1) 进行滚动，极大节省内存并提高缓存命中率。

    4. 剪枝与预处理优化

    • 炮塔伤害预处理：不要等到最后再算伤害。在转移时，如果当前格子放炮塔，直接计算它对周围已确定格子的伤害增量；如果走路径，计算它受到周围已确定炮塔的伤害。这样可以在 DP 过程中直接累加答案，避免最后遍历状态时的巨大开销。
    • 障碍特判：遇到原地图的 #，如果轮廓线上有插头，直接跳过（continue），减少无效状态转移。

    5. 最小表示法（连通性压缩）

    优化方案：不要直接记录插头的绝对编号，使用最小表示法。例如，遇到一个新的连通块，赋予当前最小的未使用编号。这能将状态数从指数级降低到卡特兰数级别，是插头DP能过题的关键。

    优化后的代码框架示例

    #include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int PRIME = 9973;
const int MAXS = 200000; // 根据实际状态数调整

struct HashTable {
    int head[PRIME], next[MAXS], sz;
    ull state[MAXS];
    int val[MAXS];

    void clear() {
        sz = 0;
        memset(head, -1, sizeof(head));
    }

    void push(ull s, int v) {
        int h = s % PRIME;
        for (int i = head[h]; ~i; i = next[i]) {
            if (state[i] == s) {
                val[i] = max(val[i], v);
                return;
            }
        }
        state[sz] = s;
        val[sz] = v;
        next[sz] = head[h];
        head[h] = sz++;
    }
} H[2];

// 状态解码与编码函数（使用位运算替代取模）
inline int get(ull s, int pos) { return (s >> (pos << 1)) & 3; }
inline ull set(ull s, int pos, int v) { return s ^ (((ull)get(s, pos) ^ v) << (pos << 1)); }

int main() {
    // 初始化与读入...
    H[0].clear();

    3天前 来自 广东

    0
暂无数据

提交答案之后，这里将显示提交结果～

首页