DAG 上的 dp

约 510 字大约 2 分钟

2026-02-20

Preface

首先介绍一下 DAG，叫做有向无环图，英文名叫 Directed Acyclic Graph，缩写是 DAG。如果你想了解更详细的内容可以前往 OI-WIKI

如下图所示，就是一个 DAG，因为它没有环路。

那么这个博客的灵感就来源于我最近做的一个 F. Parabola Independence，先来简单讲一下题目意思：

题目

给定 $n$ 个形如 $g:g(x)=ax^2+bx+c,x\in \mathbb{R}$ 的双曲线，如果称 $g_1,g_2$ 是独立的，当且仅当它们在坐标系上没有交点。

如果称一个有序函数集合 $G=\{g_1,g_2,g_3,\cdots,g_n\}$ 是 organized 的，当且仅当 $\forall ~ i,j,1\leqslant i<j\leqslant |G|$ 都满足 $g_i,g_j$ 是独立的。

现有一个集合 $F=\{f_1,f_2,f_3,\cdots,f_n\}$ 求 $\forall ~i=1,2,3,\cdots,n$ ，计算包含其 organized 的最大子集大小。如下图所示，橙色与红色不满足独立，但蓝色满足与红色独立，且与橙色也独立。

数据范围满足 $n\leqslant 3000,a,b,c\leqslant 1\times 10^9$

分析问题

首先我们先判定两个函数 $f,g$ 是否独立，我们可以通过 $f-g$ 的判别式进行判断，设两个函数分别为：

$f(x) = a_1x^2 + b_1x + c_1$
$g(x) = a_2x^2 + b_2x + c_2$

则

f-g\Longrightarrow (a_1 - a_2)x^2 + (b_1 - b_2)x + (c_1 - c_2) = 0

计算判别式 $\Delta = B^2 - 4AC$ ，若 $\Delta \geqslant 0$ ，则有交点，下面是实现方案：

hasIntersection.cc
bool hasIntersection(int a1, int b1, int c1, int a2, int b2, int c2)
{

    ll A = (ll)a1 - a2;
    ll B = (ll)b1 - b2;
    ll C = (ll)c1 - c2;

    if (A != 0)
    {

        ll delta = B * B - 4 * A * C;
        return delta >= 0;
    }
    else
    {

        if (B != 0)
        {

            return true;
        }
        else
        {

            return C == 0;
        }
    }
}