CF1481E Sorting Books 超高质量题解

fanfansann

2021-02-18 11:17:11

Solution

## E - Sorting Books 一排书架上有 $n$ 本书排成一排,每本书上有一个颜色 $a_i$,你可以每次将一本书移动到书架的最右端,如果书架上的书,颜色相同的书都排到了一块,我们就认为他是漂亮的,请问将这个书架通过上面的那一种操作排成漂亮的书架,最少需要几次操作? **Solution** 其实是超级简单的一道题 ~ 首先根据题意,先不考虑最优解,我们直接全部往右乱扔就一定能满足,但是不一定是最优解,解决最优解问题,很明显要么贪心,要么DP,要么贪心 + DP。 首先考虑贪心策略,我们一上来最直观的感受就是,如果有一种颜色,没有完全在一块,中间参杂着其他颜色的书,但是这种颜色的书的数量非常非常的多,很明显我们就可以贪心地把这种颜色中间的书移走,这些这种颜色的书就会自动合并到一块,肯定比把这种颜色的很多很多的书一个一个丢到最右边要来的快,这一点很容易想到。 所以我们来尝试找一下,有没有这种颜色的书,或者好几种,只要区间不重叠就好,数量比它中间其他颜色的书的数量还要多,也就是找到若干个区间,但是直接找区间有点困难,题目只需要我们输出最少操作次数即可,所以在有了这个完美的贪心策略以后,我们考虑DP来模拟这个过程。 我们设 $f[i]$ 表示 $i\cdots n$ 区间里不需要移动的书的最大数量,很显然答案就是 $n-f[1]$。除去不需要移动的,把剩下的按照颜色的分类丢到右边就行了。 我们想要找到的是区间里书数量最多的颜色,并且可以是很多种区间不重叠的颜色,要先找区间,所以我们先存一下每种颜色的出现的左右区间 $l_i$ 和 $r_i$ ,因为要找数量最多的那一种,所以我们再使用 $cnt$ 数组存一下每种颜色出现的次数。因为现在考虑的是逆序 DP,所以再存一下 $\text cnt\_post_i$ ,表示的是 $i\cdots n$ 之间每种颜色的书的数量。 考虑转移方程: (1)$\tt f\ [i] = \max\{f\ [i], f[i + 1]\}$ (2)$\tt f[i] = \max\{f [i], {cnt\_post} [ a[ i]]\}$ 我们取 $i\cdots n$ 里当前最优的一种颜色,也就是只选择一个区间的情况。为什么不能写成 $\tt f[i] = \max\{f [i], {cnt\_post} [ a[ i]]+f[r[a[i]]+1]\}$ 呢,也就是为什么我们不能一块加上当前颜色区间右边的最优解呢?这样看上去好像没什么毛病呀? 参见样例: ```cpp 5 1 2 2 1 3 ``` ```cpp 2 ``` 会发现如果在没有完全完整的区间的基础之上更新,就会导致几个区间重叠,得到实际上是错误的 “最优解” (3)当 $\tt l[a[i]]=i$时,$\tt f[i]=max\{cnt[a[i]]+f[r[a[i]]+1]\}$ 这里我们已经完全走完了颜色 $\tt a[i]$ 的整个区间,可以跟其他区间合并以找到最优解,也不会导致区间重叠。 这个转移方程实际上就是选择区间 $[l_{a_i},r_{a_i}]$ 里,颜色 $a_i$ 不移动,因为 $f[i]$ 存的是 $i\cdots n$ 里不需要移动的书的最大数量,所以要加上 $r_{a_i}$ 右边的 $f$ ,应该很好理解 ~ **Code** ```cpp #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <map> #include <vector> using namespace std; const int N = 5e5 + 7, mod = 1e9 + 7; typedef long long ll; typedef int itn; itn a[N], l[N], r[N]; int cnt[N], cnt_post[N]; itn n, m; int f[N]; int main() { scanf("%d", &n); for(int i = 1; i <= n; ++ i) { scanf("%d", &a[i]); if(l[a[i]] == 0) l[a[i]] = i; r[a[i]] = i; cnt[a[i]] ++ ; } for(int i = n; i >= 1; -- i) { f[i] = f[i + 1]; cnt_post[a[i]] ++ ; if(i == l[a[i]]) f[i] = max(f[i], f[r[a[i]] + 1] + cnt[a[i]]); else f[i] = max(f[i], cnt_post[a[i]]); } printf("%d\n", n - f[1]); return 0; } ``` 当然,我们上面使用逆序来求,实际上正序逆序没有任何区别 ~ ----------- 牛逼群友用线段树搞出来了... wxyyyds %%% ~~我还没看懂啥意思~~ ```cpp #include <iostream> namespace wxy{ const int N = 5e5 + 5,inf = 1e9 + 5; #define int long long int a[N],f[N],lst[N],fst[N],pre[N],cnt[N],n; struct node{int l,r,add,max;}t[N << 2]; inline void pushup(int u){t[u].max = std::max(t[u << 1].max,t[u << 1 | 1].max);} inline void pushdown(int u){ if (t[u].add){ t[u << 1].max += t[u].add; t[u << 1 | 1].max += t[u].add; t[u << 1].add = t[u << 1 | 1].add = t[u].add; t[u].add = 0; } } inline void build(int u,int l,int r){ t[u].l = l; t[u].r = r; t[u].add = 0; if (l == r){t[u].max = cnt[l]; return;} int mid = l + r >> 1; build(u << 1,l,mid); build(u << 1 | 1,mid + 1,r); pushup(u); } inline void cge(int u,int l,int r,int v){ if (t[u].l == l && t[u].r == r){ t[u].max += v; t[u].add += v; return; } int mid = t[u].l + t[u].r >> 1; pushdown(u); if (r <= mid) cge(u << 1,l,r,v); else if (l > mid) cge(u << 1 | 1,l,r,v); else {cge(u << 1,l,mid,v); cge(u << 1 | 1,mid + 1,r,v);} pushup(u); } inline int query(int u,int l,int r){ if (t[u].l == l && t[u].r == r) return t[u].max; pushdown(u); int mid = t[u].l + t[u].r >> 1; if (r <= mid) return query(u << 1,l,r); else if (l > mid) return query(u << 1 | 1,l,r); else return std::max(query(u << 1,l,mid),query(u << 1 | 1,mid + 1,r)); } inline void main(){ std::cin >> n; for (int i = 1; i <= n; i++) std::cin >> a[i]; for (int i = 1; i <= n; i++){ pre[i] = lst[a[i]]; lst[a[i]] = i; cnt[a[i]]++; } int pos = n; for (int i = n; i >= 1; i--){ if (a[i] == a[n]) pos = i; else break; } int cr = cnt[a[n]] - (n - pos + 1); for (int i = 1; i <= n; i++) if (i != a[n]) cr += cnt[i]; for (int i = 1; i <= n; i++) if (fst[a[i]] == 0) fst[a[i]] = i; int premax = 0; for (int i = 1; i <= n; i++){ if (fst[a[i]] == i){ f[i] = 1; f[i] = std::max(f[i],premax + 1); }else{ f[i] = f[pre[i]] + 1; } if (lst[a[i]] == i) premax = std::max(premax,f[i]); } int ct = 0; int ans = n - f[n]; for (int i = 1; i <= n; i++){ if (a[i] == a[n]) continue; if (lst[a[i]] == i) ans = std::min(ans,cr - f[i]); } for (int i = 1; i <= n; i++) if (cnt[i] == 0) cnt[i] = -inf; build(1,1,n); for (int i = 1; i <= n; i++){ cge(1,a[i],a[i],-1); if (lst[a[i]] != i) continue; if (a[i]-1>=1)cge(1,1,a[i]-1,f[i]); if (a[i]+1<=n)cge(1,a[i]+1,n,f[i]); ans = std::min(ans,n - query(1,1,n)); if (a[i]-1>=1)cge(1,1,a[i]-1,-f[i]); if (a[i]+1<=n)cge(1,a[i]+1,n,-f[i]); } std::cout << ans; } }signed main(){wxy::main(); return 0;} ```