专栏文章

官解：Terrorists

JJZJR_A_0
P15250题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mlgxxws1
此快照首次捕获于
2026/02/11 02:35
上周
此快照最后确认于
2026/02/11 02:35
上周
查看原文

前置知识

  • DP
  • 矩阵加速

算法 1

考虑暴力。对每一天枚举点对，朴素实现 DP 的复杂度为 O(N⋅m2)O(N \cdot m^2)。
期望得分 20pts20pts。

算法 2

不难想到记录能够转移的点对来优化转移。
由于数据随机，转移方案数应该是蛮少的。
可能有点卡常，但确实能过。
期望得分 50pts50pts。

算法 3

按照算法 22 的想法，既然转移点对都是固定的，那么这个 DP 就是固定的线性递推关系。
考虑矩阵加速，时间复杂度为 O(m3log⁡N)O(m^3\log N)。
期望得分 100 pts\text{100 pts}。

code

避免有人说算法 22 过不了，我粘个码。
CPP
int run[105][105];
int tot[105];
inline void Add(int &a, int b){
    a += b;
    (a >= MOD ? a -= MOD : a);
}
int f[105], lst[105];
int main() {
    for (int j = 0; j < m; ++ j) {
            for (int k = 0; k < m; ++ k) {
                if (persons[j].t <= persons[k].t && persons[j].c >= persons[k].c) {
                    if (persons[j].g == 'g' || persons[j].l <= persons[k].l) {
                        run[j][++ tot[j]] = k;
                    }
                }
            }
        }
    while (N --) {
        memcpy(lst, f, sizeof(int) * m);
        memset(f, 0, sizeof(int) * m);
        for (int j = 0; j < m; ++ j) {
            for (int p = tot[j]; p;){
                Add(f[j], lst[run[j][p --]]);
            }
        }
    }
    for (int i = 0; i < m; i++)
        Add(ans, f[i]);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...