贪心？动态规划？都试试！
Sweetlemon
2019-10-29 16:48:57
#### 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 的日报](https://www.luogu.org/blog/Chanis/super-BIT)。
那么有没有别的做法呢？
看这个转移方程，似乎有一点“单调”的意思。
我们要求的东西是一个“后缀最小值”，因此“标号大、代价小”的状态会覆盖“标号小、代价大”的状态，我们的数组应该是单调递增的。
查找时在数组中寻找标号不小于 $\mathrm{pre}[i]$ 的第一个元素，就是我们寻找的最小代价，加上 1 就是 $f[i]$ 的值。
插入时，如果数组中存在着“标号比 $i$ 小、代价还比 $f[i]$ 大”的元素，就会被 $f[i]$ 覆盖，从而可以把被覆盖的状态删除。这些状态分布在 $f[1...i]$ 的后半部分，因此从 $f[i]$ 往前找，一直找到不能删就停下。
数组中删除元素？当然不行！
根据斜率优化的经验，这里我们使用一个 set 来维护，不断 `lower_bound` 和 `erase` 即可。于是这题就解决了。
----
可是！真的不能贪心吗？
我们换个思路。仍然使用“买 $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 天生比较慢；至于我的贪心为什么这么慢……还是人傻常数大吧？
##### 贪心
```cpp
#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
```cpp
#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
```cpp
#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 三个函数的实现
```