首页 > 其他分享 >slope trick

slope trick

时间:2024-02-14 22:35:06浏览次数:33  
标签:slope tmp 函数 min int trick 最小值 平移

slope trick

对于一类 DP 问题,DP 状态是二维的 \(f_{i,j}\),且 \(f_i\) 可以看作一个关于 \(j\) 的线性的连续凸分段函数

转移时可以直接维护这个函数而优化复杂度

维护操作

以下凸函数为例

我们维护第一段函数的斜率 \(k\),用数据结构维护出斜率每变化 \(1\) 时的转折点的可重集

注意如果某点处斜率变化了不止 \(1\),就得插入对应数量的点

例如,函数 \(f(x)=|x-a|\),我们维护 \(k=-1\),数据结构中存 \(2\) 个 \(a\),表示 \(a\) 处斜率从 \(-1\to0\to1\)

取最值

由于函数下凸,最小值点就是 \(k=0\) 时的点

因此用 \(L\) 堆存从小到大 \(k\le 0\) 的转折点,\(R\) 堆存从小到大 \(k>0\) 的转折点

此时 \(L\) 堆和 \(R\) 堆队头中间的一段 \(k=0\),就是最小的

加函数

整体加一个下凸函数,我们把开头的 \(k\) 加上那个开头对应的 \(k\),直接暴力插入新的转折点即可

前缀/后缀取 \(\min\)

函数是一个下凸函数,当 \(k\le0\) 时,前缀 \(\min\) 就是它自己,当 \(k>0\) 时,前缀 \(\min\) 变为 \(k=0\) 时的值

因此直接把 \(R\) 堆中的转折点丢掉即可

平移

如 \(f(x)\) 变为 \(f(x-l)\),向右平移 \(l\),则是在堆上打 \(tag\),表示堆中的值加上 \(tag\) 后才是真实的横坐标

此时 \(tag\) 应 \(\gets tag + l\)

把新的转折点插入堆之前注意 \(-tag\)

限定定义域

上面维护的函数定义域都是 \((-\infty,\infty)\),但是有些题中限制了定义域,即转移范围

求 \(x\in[l,r]\) 的最值时,最值点可能在 \(l/r\) 处

那么实现时将转折点加入堆时对 \(l\) 取 \(\max\),对 \(r\) 取 \(\min\),这样不会影响函数在定义域内的取值

取出时有人说不用再取,但我试了一下,好像还是要取 \(\max/\min\) 才过的去?不知道什么情况(

求出答案

这里就直接采用倒推方案求答案的方法

首先最后我们得到的函数,它上面的每个点都是合法取值,因此我们直接取取到最小值的点,一定对应一组方案

但是前面转移的过程中,不是每个的最小值点都是方案

因此在每次转移时记录最小值点,倒推回去,如果当前函数的最小值点符合要求,就直接取它,否则根据题目的性质,贪心选取离最小值点近的转折点,这样能尽可能满足后面的,不会使答案变差

应用

P4331 [BalticOI 2004] Sequence 数字序列

模板题,将每个 \(a_i\) 减去 \(i\),限制变为单调不降

朴素 DP 是 \(f_{i,j}=\min_{k\le j}(f_{i-1,k}+|j-a_i|)\)

发现绝对值函数是凸的,凸函数加凸函数仍是凸的,因此用 slope trick,维护整体加函数,取前缀 \(\min\) 操作

int main()
{
    read(n);
    for(int i = 1; i <= n; ++i) read(a[i]), a[i] -= i;
    for(int i = 1; i <= n; ++i)
    {
        --k, heap.push(a[i]), heap.push(a[i]);
        while(heap.size() + k > 0)  heap.pop();
        b[i] = heap.top();
    }
    for(int i = n - 1; i > 0; --i)  b[i] = min(b[i + 1], b[i]);
    for(int i = 1; i <= n; ++i) ans += llabs(a[i] - b[i]);
    print(ans), putchar('\n');
    for(ll i = 1; i <= n; ++i)  print(i + b[i]), putchar(' ');
    return 0;
}

P4272 [CTSC2009] 序列变换

上一题的升级版

\[f_{i,j}=\min_{k\in[a,b],j\in[L,R]}(f_{i-1,j-k}+|X_i-j|) \]

加上了范围的限制,首先分析平移 \(k\) 的影响,记函数最小值段的端点为 \(l,r\)

当 \(x< l\) 时,由于单调不增,平移的越少越好,向右平移 \(a\)

当 \(x>r\) 时,由于单调不降,平移的越多越好,向右平移 \(b\)

至于中间的段,平移后都是最小值段,不变,不用单独考虑

因此在 \(L\) 堆,\(R\) 堆上分别打平移标记

最后是经典的加函数与取前缀最小值的操作

由于题目保证有解,因此位置 \(i\) 最小为 \(L=(i-1)a+1\),最大为 \(R=Q\)

注意此处答案的构造,如果最小值点取不到,就贪心调整为合法的离它最近的

int main()
{
    read(n, lim, a, b);
    for(int i = 1; i <= n; ++i) read(p[i]);
    for(int i = 1; i <= n; ++i)
    {
        tagl += a, tagr += b, --k; // k=0 拐点左侧向右平移 a, 右侧向右平移 b
        while(!rhp.empty() && k + (ll)lhp.size() < 0)   lhp.push(rhp.top() + tagr - tagl), rhp.pop();
        ll tr = min(max(p[i], (i - 1) * a + 1), lim); // 先让拐点在范围内,调整不影响范围内的函数值
        lhp.push(tr - tagl), lhp.push(tr - tagl); // 加上函数
        while(k + (ll)lhp.size() > 0)   rhp.push(lhp.top() + tagl - tagr), lhp.pop();
        q[i] = max((i - 1) * a + 1, min(lhp.top() + tagl, lim));
    }
    ans += llabs(q[n] - p[n]); // 还原真实值
    for(int i = n - 1; i > 0; --i)
    {
        q[i] = max(q[i + 1] - b, min(q[i], q[i + 1] - a));
        ans += llabs(q[i] - p[i]);
    }
    printf("%lld", ans);
    return 0;
}

CF104821D Red Black Tree

好,上树了

naive 的想法是设 \(f_{x,i}\) 表示 \(x\) 子树内有 \(i\) 个黑点时的最小代价,转移为 \(f_{x,i}=\min_{c=0/1} cost(x,c)+\sum_y f_{y,i-c}\),表示枚举 \(x\) 是红点还是黑点,增加相应代价,然后是黑点则 \(y\) 子树内要少取一个黑点

可以归纳证明/感性理解 \(f_x\) 为凸函数

而且发现这个函数定义域是 \([0,x\text{到子树内最浅叶子的距离}]\)

根据长链剖分的复杂度分析,每次合并两棵子树,代价是取 \(\min\),总复杂度均摊线性

那么可以暴力合并函数,但还有加上 \(cost(x,c)\),平移后两个函数取 \(\min\) 的操作

因为 \(cost(x,c)=0/1\),而函数不为 \(0\) 的斜率绝对值最小是 \(1\),因此左边的平移后肯定不优,右边的平移后肯定更优

那么 \(x\) 为黑点时就直接可以看作是在最小值段左端插入一段斜率为 \(-1\) 的函数,为红点时在最小值段右端插入斜率为 \(1\) 的,同时也顺便完成了平移操作

既然横坐标范围小,我们直接维护各个横坐标处各段函数的斜率

维护两个 vector,一个存负斜率,一个反过来存正斜率,插入就直接在末尾插入,还维护一下 \(0\) 的个数

合并就是对位相加,计算答案时,由于我们已知 \(f_{x,0}\) 的值就是子树内黑点个数,因此记录负斜率之和即可算出最小值

注意合并时第一个不能直接 copy,万一是长链就寄了,维护一下编号

精细实现复杂度 \(O(n)\)

struct slopetrick
{
    vector<int> fu, zh;
    int num, sum;
    void clear()    {fu.clear(), zh.clear(), num = sum = 0;}
    void ins(int val)   {val > 0 ? zh.pb(val) : (sum += val, fu.pb(val));}
    int operator ()(int x)const
    {
        if(x < fu.size())   return fu[x];
        if(fu.size() + num > x) return 0;
        return zh[zh.size() - (x - fu.size() - num) - 1];
    }
    void build(vector<int> x)
    {
        clear();
        for(int i : x)
            if(i < 0)   fu.pb(i), sum += i;
            else if(i > 0)  zh.pb(i);
            else    ++num;
        reverse(zh.begin(), zh.end());
    }
    int size()const {return fu.size() + num + zh.size();}
}a[N];
vector<int> operator + (const slopetrick &x, const slopetrick &y)
{
    vector<int> tmp;
    for(int i = 0; i < lim; ++i)   tmp.pb(x(i) + y(i));
    return tmp;
}
vector<int> operator + (const vector<int> &x, const slopetrick &y)
{
    vector<int> tmp;
    for(int i = 0; i < lim; ++i)   tmp.pb(x[i] + y(i));
    return tmp;
}
void clear()
{
    for(int i = 1; i <= n; ++i) 
    {
        edge[i].clear(), a[i].clear();
        dep[i] = N, id[i] = i, siz[i] = fa[i] = ans[i] = mson[i] = col[i] = 0;
    }
}
void dfs(int x)
{
    siz[x] = col[x];
    if(!edge[x].size())
    {
        a[id[x]].ins(col[x] ? -1 : 1), dep[x] = 1, ans[x] = 0;
        return;
    }
    for(int y : edge[x])
    {
        dfs(y), siz[x] += siz[y];
        if(dep[y] + 1 < dep[x]) mson[x] = y, dep[x] = dep[y] + 1;
    }
    id[x] = id[mson[x]], lim = dep[x] - 1;
    if(edge[x].size() > 1)
    {
        int fir = 0;    vector<int> tmp;
        for(int y : edge[x])
            if(y != mson[x])    
            {
                if(fir) tmp = tmp + a[id[y]];
                else    fir = y, tmp = a[id[x]] + a[id[y]];
            }
        a[x].build(tmp), id[x] = x;
    }
    a[id[x]].ins(col[x] ? -1 : 1), ans[x] = siz[x] + a[id[x]].sum;
}
void mian()
{
    read(n), reads();
    clear();
    for(int i = 0; i < n; ++i)  col[i + 1] = s[i] - '0';
    for(int i = 2; i <= n; ++i) read(fa[i]), edge[fa[i]].pb(i);
    dfs(1);
    for(int i = 1; i <= n; ++i) print(ans[i]), i < n ? space() : endl();
}

标签:slope,tmp,函数,min,int,trick,最小值,平移
From: https://www.cnblogs.com/KellyWLJ/p/18015724

相关文章

  • 【Trick】标记永久化
    1.理论线段树使用来维护区间信息的数据结构。回想一下,是否还记得线段树的pushdown操作。在区间修改区间查询中,由于区间修改时信息不一定能传达到位,需要使用lazytag将修改信息打在非叶子节点上(其实可以不用,但时间复杂度错误)。这样一来,当查询的区间在其子区间时,可以把打在当......
  • tricks I
    1.P2824排序碰见这种只有最后有一个查询的问题我们可以考虑二分最后的答案。具体地,对于当前\(mid\),把所有小于\(mid\)的设为\(0\),其他的设为\(1\)。此时我们只需要维护最后的位置是否大于\(mid\)就好。那么每次升降序的排序就很好办了。我们用线段树维护一个区间和,也......
  • 最近见到的 trick 汇总
    见到啥写啥吧qwq历年省选/NOI/NOIP/其他官方考试已经标出。OEIS把样例粘贴到OEIS上。www.oeis.org怎么你了。CF1916H1/H2数学容斥原理求解问题。\[|S_1\cupS_2\cup\cdots\cupS_n|=\sum_{i=1}^n|S_i|+\sum_{k=2}^n(-1)^{k-1}\sum_{1\leqi_1<i_2<\cdots<i_k\leqn}|S......
  • Essay - OI tricks
    ......
  • trick 集合
    trick集合1.基础判断是否\(\foralli\)有\(x<a_i\):转化为是否\(x<\min(a_i)\)。大于类似。P9868&题解,ABC223F&题解括号序列:是括号序列的条件:总共的左括号和右括号数量相等;任意前缀的左括号数量\(\ge\)右括号数量。若将序列中左括号看作......
  • [CF30E] Tricky and Clever Password 题解
    [CF30E]TrickyandCleverPassword题解注意到一个合法字符串首尾相同,考虑用S的反转和S跑KMP。对于只有一个串,暴力manacher即可。匹配到某一位置\((i,j)\)时,查询区间最长的奇回文串长度,用二分+ST表解决,因为回文串不能超过区间长度。//Problem:TrickyandCle......
  • 【CF30E】Tricky and Clever Password 题解(manacher + exKMP)
    manacher+exKMP+二分。感觉是最粗暴的方法,想出来之后自己硬莽了4k,荣获题解区最长。Solution约定:下文所提及到的所有的回文串,均指奇长度回文串。显然把题目拆成两个部分,中间的回文串,以及两边相同的连续子串。考虑一下从哪个入手比较好。忘记是咋想的了,易得从两边相同......
  • Generative AI generates tricky choices for managers
     GenerativeAIgeneratestrickychoicesformanagersTransformationaltechnologiescanbeverytrying   THEREMARKABLEcapabilitiesofgenerativeartificialintelligence(AI)areclearthemomentyoutryit.Butremarkablenessisalsoaproble......
  • Trick 信友队2023
    就是收集了trick。线段树的扩展用法单侧递归线段树历史最大值线段树(卢瑞恩)\(\text{SegmentTreeBeats}\)其中历史最大值线段树和\(\text{SegmentTreeBeats}\)的历史最值操作可以结合。如果由区间修改操作会影响\(\text{SegmentTreeBeats}\)的势能,具体的,每操作......
  • CV常用Tricks
    训练CV比赛常用Tips&Tricks目录引言1.图像增强颜色增强RGBNormBlackandWhiteBenGraham:Grayscale+GaussianBlurHue,Saturation,BrightnessLUVColorSpaceAlphaChannelYZColorSpaceLumaChromaCIELabYUVColorSpaceCenterCropFlippingsRandom......