Sweetlemon 的博客

Sweetlemon 的博客

贪心?动态规划?都试试!

posted on 2019-10-29 16:48:57 | under 题解 |

LGR-062, C, 小 C 与桌游

这是一道有意思的题目。

题意简述:求 DAG 的一个拓扑序,使得拓扑序列的前缀最大值的变化次数尽可能多 / 少。

首先看尽可能多的情况。考虑贪心,把拓扑排序的队列改为优先队列,每次都取当前入度为零(称之为“可访问”)的点中最小的一个进行访问。可以用调整的方法证明这个贪心策略的最优性——如果这一步不访问最小的那一个点 $u$ ,而是访问另一个点 $v$ ,那么把访问 $u$ 的位置提到访问 $v$ 以前,这个拓扑序仍合法,并且答案会变大。

那么尽可能少的情况呢?我们是不是也可以用类似的贪心,每次都取当前可访问点中最大的一个进行访问呢?

考虑这个例子:

简单贪心反例

如果每次取可访问点中最大的一个来访问,那么自然会依次选中 $1,3,5,4,2,6$ ,总代价是 $4$ ;但是如果选择拓扑序 $1,2,6,3,5,4$ ,总代价则只有 $3$ 。也就是说,大的点可能会被掩盖在小的点后面,使得我们的贪心不正确!

或者可以从贪心证明的角度来思考。尽可能多的情况下,访问了较小的不会影响访问较大者的贡献;但在尽可能少的情况下,访问较大者会影响访问较小者的贡献;因此,这两个存在本质的不同,不能直接生搬硬套。

怎么办呢?如果贪心不行,我们不妨考虑 dp?

设 $f[i]$ 表示访问到的最大的点是 $i$ 时的最小代价,那么 $f[0]=0$ ,答案就是 $f[n]$ 。这个状态其实是有冗余的——比如上图中 $f[4]$ 就没有意义,任何时刻访问到的最大的点都不可能是 $4$ 。不过这个状态对于表示问题的当前情况来说也算是足够了,就姑且这么使用吧。

设 $\mathrm{pre}[i]$ 表示 $i$ 的所有前置点 $j$ (即存在路径 $j\rightarrow i$ 的点 $j$ )的最大标号,例如上图中 $\mathrm{pre}[1]=0,\mathrm{pre}[6]=2,\mathrm{pre}[4]=5$ 。不难发现, $f$ 数组仅对于 $\mathrm{pre}[i]<i$ 的点有意义,我们把这些点称为“关键点”;并且对于任意点 $i$ , $\mathrm{pre}[i]$ 都是关键点。 $\mathrm{pre}$ 数组可以通过 DAG 上 dp 简单地求出。

考虑所有关键点 $i$ , $f[i]=f[\mathrm{pre}[i]]+1$

……吗?

再考虑这个例子。

转移方程反例

如果 $f[i]=f[\mathrm{pre}[i]]+1$ ,那么 $f[1]=1,f[2]=2,f[3]=3,f[4]=4,f[5]=2,f[6]=5$ 。

但是事实上,访问到 $6$ 的最小代价实际上是 $3$ ——访问顺序可以是 $1,5,2,3,4,6$ !

访问点 $i$ 的条件是 $i$ 的前置点都已经被访问,那么只要“当前已经访问的点的最大值”不小于 $\mathrm{pre}[i]$ ,我们就已经可以把 $i$ 的前置点访问完毕了!可以这么理解:假如我们已经买好了 $k$ 级票,买好后可以免费访问 $k$ 级及以下的点,那么只要 $k\ge \mathrm{pre}[i]$ , $i$ 的前置点就都在可免费访问的范围内。

因此,事实上 $f[i]=\min(f[k])+1,\mathrm{pre}[i]\le k<i$ 。这里我们严格按照定义,对于 $k>i$ 的情况不在 $f[i]$ 处考虑而是在 $f[k]$ 处考虑。

这个 dp 怎么算呢?

我会动态区间最小值!不就是棵线段树嘛!或者也可以用树状数组,代码好写,常数较小,但是多一个 $\log$ 。树状数组方面的实现可以详见Chanis 的日报

那么有没有别的做法呢?

看这个转移方程,似乎有一点“单调”的意思。

我们要求的东西是一个“后缀最小值”,因此“标号大、代价小”的状态会覆盖“标号小、代价大”的状态,我们的数组应该是单调递增的。

查找时在数组中寻找标号不小于 $\mathrm{pre}[i]$ 的第一个元素,就是我们寻找的最小代价,加上 1 就是 $f[i]$ 的值。

插入时,如果数组中存在着“标号比 $i$ 小、代价还比 $f[i]$ 大”的元素,就会被 $f[i]$ 覆盖,从而可以把被覆盖的状态删除。这些状态分布在 $f[1...i]$ 的后半部分,因此从 $f[i]$ 往前找,一直找到不能删就停下。

数组中删除元素?当然不行!

根据斜率优化的经验,这里我们使用一个 set 来维护,不断 lower_bounderase 即可。于是这题就解决了。


可是!真的不能贪心吗?

我们换个思路。仍然使用“买 $k$ 级票”的情景,即必须按照拓扑序访问节点,访问节点时要先买票;买一次票的代价是 $1$ ,买 $k$ 级票可以访问所有标号不大于 $k$ 的节点;买票时只能买当前可以访问的节点,即当前入度为 0 的节点。

算法刚开始时,我们只买了 $0$ 级票(也就是还没有买票),什么节点都不能访问。这时候当然必须买票了,不交钱不行啊!于是我们只能交些车船费(花费 $1$ 的代价),买一张票。

买票的时候你看到了这几张票:J 级票, $1$ 元;S 级票, $1$ 元;N 级票, $1$ 元;I 级票, $1$ 元。假如这四张票都能买,那么你选择买哪一张呢?当然是最高级的 I 级票啦,毕竟车船费都是一样的,肯定要买适用范围最广的 I 级啦。

这就是我们的贪心策略——在必须买票的时候,买可以买的最高级的票。

翻译成原题语言,就是当 目前所有可访问的节点标号 都大于 访问过的节点的最大标号,也就是必须要花费 $1$ 的代价时,访问 可访问点 中 标号最大 的那一个。

等一下!这和原来的贪心策略有什么区别?当然是在前提条件上啦。

原来的策略是,在访问一个新的点时,选择可访问的标号最大的点。

现在的策略是,在必须花费代价才能访问新的点时,选择可访问的标号最大的点。

现在的策略的好处就是“物尽其用”,利用原来消耗过的代价,尽可能地访问更多的点,争取暴露出“更高级的票”,也就是尽量地把标号大的点加入到可访问点的集合中。这样就解决了原来贪心策略中“大的点被小的点掩盖”的问题。

于是我们的算法就是:

  1. (此时必须买票)选择可访问的点中标号最大的进行访问,代价加 1
  2. (此时利用刚买的票)访问可访问点中所有标号小于“最大标号”的点
  3. 重复上述两个步骤,直到所有的点都被访问

我们用什么来维护“可访问点”的集合呢?要支持取最大值,取所有“不超过 $x$ ”的数值……

既然是集合,那就用 set 吧。取最值用 rbegin,取“不超过 $x$ 的数值”用 lower_bound

当然,还可以用两个堆。我们把可访问点同时加入最大堆和最小堆中,第 1 步时取最大堆堆顶,第 2 步不断从最小堆堆顶取元素,直到堆顶的标号大于“最大标号”。注意,需要用标记数组防止重复访问同一个点。这道题的查询是一个“两端”型的,也就是要从值域的两端取东西,那么两个堆拼起来不就像一个两端开口的容器吗?正符合我们的要求。

于是这题终于完美解决了。这道题启示我们,贪心和动态规划常常相互配合,动态规划能处理贪心难以解决的问题,贪心能优化动态规划的状态设计,降低时间复杂度。当然,我们也要考虑从贪心和动态规划本身进行优化,尤其是优化贪心策略、优化状态表示和状态转移。

其实,尽可能多的情况也可以用 dp 解决(这个 dp 应该是比“尽可能少的情况”简单的),也不妨思考一下。

下面附各种做法(贪心、树状数组优化 dp、set 单调优化 dp)的代码。

速度的话,可能我的常数比较大,测试结果是 (所有测试点时间之和) 贪心 1.33s, set 1.92s, 树状数组 941 ms(均无 -O2,加 -O2 后差异不大)。可以看到,虽然树状数组的复杂度多一个 $\log$ ,但是由于这个 $\log$ 是最坏情况,并不常能取到;且常数较小,因此实际速度还是较快的。而 set 天生比较慢;至于我的贪心为什么这么慢……还是人傻常数大吧?

贪心
#include <cstdio>
#include <cctype>
#include <functional>
#include <algorithm>
#include <queue>
#define MAXIOLG 25
#define MAXN 500005
#define MAXM 1000005
#define INf 114514
#define INF 1919810

using namespace std;

typedef long long ll;
typedef long double ld;
typedef ll io_t;

io_t shin[MAXIOLG];
io_t seto(void); //快读
void ayano(io_t x,char spliter='\n'); //快写

priority_queue<int,vector<int>,greater<int> > q; //小根堆
priority_queue<int,vector<int>,less<int> > q2; //大根堆

int fst[MAXN],nxt[MAXM],edges=0; //存图
int g[MAXM];
int ind[MAXN],visited[MAXN]; //入度, 访问标记

void addedge(int u,int v); //加边

int main(void){
    int n,m;
    n=seto(),m=seto();
    while (m--){
        int u,v;
        u=seto(),v=seto();
        addedge(u,v),ind[v]++;
    }

    int ans1=0,ans2=0;
    //先计算尽可能大情况的答案 ans1
    for (int i=1;i<=n;i++)
        (!ind[i])?(q.push(i)):(void());
    int tx=0; //当前访问过的最大的节点
    while (!q.empty()){
        int nowv=q.top(); //要访问的节点
        q.pop();
        if (nowv>tx)
            tx=nowv,ans1++; //更新答案
        for (int ei=fst[nowv];ei;ei=nxt[ei]){
            int v=g[ei];
            ind[v]--;
            (!ind[v])?(q.push(v)):(void());
        }
    }
    ayano(ans1); //输出第一个答案
    //再计算尽可能小情况的答案 ans2
    for (int i=1;i<=n;i++)
        for (int ei=fst[i];ei;ei=nxt[ei])
            ind[g[ei]]++; //重新统计入度
    for (int i=1;i<=n;i++)
        (!ind[i])?(q.push(i),q2.push(i)):(void()),
        visited[i]=0; //注意要同时插入到两个堆里
    tx=0;
    while (!q2.empty()){
        //取大根堆堆顶, 买票
        int nowv=q2.top();
        q2.pop();
        if (visited[nowv])
            continue;
        visited[nowv]=1;
        (nowv>tx)?(ans2++,tx=nowv):(0);
        //访问这个节点
        for (int ei=fst[nowv];ei;ei=nxt[ei]){
            int v=g[ei];
            ind[v]--;
            (!ind[v])?(q.push(v),q2.push(v)):(void());
        }
        while ((!q.empty()) && (nowv=q.top())<=tx){
            //取小根堆堆顶进行访问, 充分利用票
            q.pop();
            if (visited[nowv])
                continue;
            visited[nowv]=1;
            for (int ei=fst[nowv];ei;ei=nxt[ei]){
                int v=g[ei];
                ind[v]--;
                (!ind[v])?(q.push(v),q2.push(v)):(void());
            }
        }
    }
    ayano(ans2); //输出第二个答案
    return 0;
}

void addedge(int u,int v){
    edges++;
    g[edges]=v;
    nxt[edges]=fst[u],fst[u]=edges;
}

io_t seto(void){
    io_t x=0;
    char ch=getchar();
    int symbol=0;
    while (!isdigit(ch))
        (ch=='-')?(symbol=1):(0),ch=getchar();
    while (isdigit(ch))
        x=(x*10)+(ch-'0'),ch=getchar();
    return (symbol)?(-x):(x);
}
void ayano(io_t x,char spliter){
    if (!x){
        putchar('0'),putchar(spliter);
        return;
    }
    if (x<0)
        putchar('-'),x=-x;
    int len=0;
    while (x){
        io_t d=x/10;
        shin[len++]=x-d*10;
        x=d;
    }
    while (len--)
        putchar(shin[len]+'0');
    putchar(spliter);
}
树状数组求区间最值的 dp
#include <cstdio>
#include <cctype>
#include <functional>
#include <algorithm>
#include <queue>
#define MAXIOLG 25
#define LOWBIT(x) ((x)&(-(x)))
#define MAXN 500005
#define MAXM 1000005
#define INf 114514
#define INF 1919810
using namespace std;

typedef long long ll;
typedef long double ld;
typedef ll io_t;

io_t shin[MAXIOLG];
io_t seto(void);
void ayano(io_t x,char spliter='\n');

priority_queue<int,vector<int>,greater<int> > q;

int n;
int fst[MAXN],nxt[MAXM],edges=0;
int g[MAXM];
int ind[MAXN];
int pre[MAXN]; //上文所述的 pre 数组
int f[MAXN]; //上文所述的动态规划 f 数组
int ftarr[MAXN]; //用于存储 f 最小值的树状数组

int query(int l,int r); //树状数组查询区间最小值, O(log n log n)
void update(int x,int v); //简化版的树状数组更新区间最小值
void addedge(int u,int v); //加边

int main(void){
    int m;
    n=seto(),m=seto();
    while (m--){
        int u,v;
        u=seto(),v=seto();
        addedge(u,v),ind[v]++;
    }
    for (int i=1;i<=n;i++)
        (!ind[i])?(q.push(i),pre[i]=0):(0),
        f[i]=ftarr[i]=INF; //初始化, f 和树状数组都初始化为 INF
    int ans1=0; //第一行输出的答案
    int tx=0; //当前访问的最大节点(在计算第一个答案时用)
    //由于 dp 可以按照任意拓扑序计算
    //因此本程序中两个答案的计算同时进行
    while (!q.empty()){
        int nowv=q.top();
        q.pop();
        //下面一部分用于 dp
        if (nowv>pre[nowv]){
            //关键点
            f[nowv]=query(pre[nowv],nowv-1)+1; //查询区间最值, 加1
            update(nowv,f[nowv]); //插入到树状数组中进行更新
        }
        int tpre=max(pre[nowv],nowv);
        //下面一部分用于贪心
        if (nowv>tx)
            tx=nowv,ans1++;
        for (int ei=fst[nowv];ei;ei=nxt[ei]){
            int v=g[ei];
            pre[v]=max(pre[v],tpre); //在访问的同时更新 pre
            ind[v]--;
            (!ind[v])?(q.push(v)):(void());
        }
    }
    //输出两个答案
    ayano(ans1);
    ayano(f[n]);
    return 0;
}

int query(int l,int r){
    //查询区间 [l,r] 的最小值
    if (!l)
        return 0; //注意树状数组遇到下标 0 会出事, 所以提前处理; f[0]=0
    int ans=INF;
    while (r>=l){
        int t=r^LOWBIT(r); //相当于 t=r-LOWBIT(r)
        if (t>=l)
            ans=min(ans,ftarr[r]),r=t;
        else
            ans=min(ans,f[r]),r--;
    }
    return ans;
}

void update(int x,int v){
    //注意,这是简化版的更新函数
    //由于本题中树状数组中的值只会变小不会变大
    //所以可以像求和一样进行更新, 更新复杂度 O(log n)
    //但是一般的 值有可能变大的问题不能这么写
    //必须对所有有影响的点重新计算最值, 更新复杂度 O(log n log n)
    while (x<=n)
        ftarr[x]=min(ftarr[x],v),
        x+=LOWBIT(x);
}
//以下略去了 addedge, seto, ayano 三个函数的实现

set 优化 dp

#include <cstdio>
#include <cctype>
#include <functional>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#define MAXIOLG 25
#define MAXN 500005
#define MAXM 1000005
#define INf 114514
#define INF 1919810

using namespace std;

typedef long long ll;
typedef long double ld;
typedef ll io_t;

io_t shin[MAXIOLG];
io_t seto(void);
void ayano(io_t x,char spliter='\n');

priority_queue<int,vector<int>,greater<int> > q; //用于贪心的小根堆
set<pair<int,int> > st; //pair 自带比较函数

int fst[MAXN],nxt[MAXM],edges=0;
int g[MAXM];
int ind[MAXN];
int pre[MAXN];
int f[MAXN];

void addedge(int u,int v);

int main(void){
    int n,m;
    n=seto(),m=seto();
    while (m--){
        int u,v;
        u=seto(),v=seto();
        addedge(u,v),ind[v]++;
    }
    for (int i=1;i<=n;i++)
        (!ind[i])?(q.push(i),pre[i]=0):(0),
        f[i]=INF;
    int ans1=0;
    int tx=0;
    f[0]=0;
    st.insert(make_pair(0,0));
    while (!q.empty()){
        int nowv=q.top();
        q.pop();
        int tpre=pre[nowv];
        //以下是 dp
        if (nowv>tpre){
            //计算 f 值; first 保存"值"——标号,second 保存"下标"——代价
            f[nowv]=st.lower_bound(make_pair(tpre,0))->second+1;
            int tf=f[nowv];
            //下面将把 f[nowv] 插入到 set 中
            //找到标号小于 nowv 且代价大于 nowv 的状态
            auto it=st.lower_bound(make_pair(nowv,0));
            // 不断删除
            while ((it!=st.begin() && (it--,1)) && (it->second > tf))
                st.erase(it),it=st.lower_bound(make_pair(nowv,0));
            //插入
            st.insert(make_pair(nowv,tf));
        }
        tpre=max(tpre,nowv);
        //以下是贪心
        if (nowv>tx)
            tx=nowv,ans1++;
        for (int ei=fst[nowv];ei;ei=nxt[ei]){
            int v=g[ei];
            pre[v]=max(pre[v],tpre);
            ind[v]--;
            (!ind[v])?(q.push(v)):(void());
        }
    }
    ayano(ans1);
    ayano(f[n]);
    return 0;
}
//以下略去了 addedge, seto, ayano 三个函数的实现