Codeforces 1197E Culture Code
题目链接
https://codeforces.com/contest/1197/problem/E
题目大意
给你 $n$ 个带有内外半径的俄罗斯套娃，当且仅当一个套娃的外半径小于等于另一个套娃的内半径的时候它才能被套进去。要求你选择的套娃的子集必须能套起来且不能将任何一个不在子集中的套娃加进去。问使得留出的空位最少的选择方法有多少种。
题目分析
考虑使用 $DP$ 来解决问题。按照内半径大小依次处理每个套娃。令 $f[i]$ 为最外层为 $i$ 的套娃的最小留空，那么显然有 $f[i] = \min\limits_{out_j \leq in_i}(f[j] + in_i – out_j)$ 。
但是这个 $DP$ 方程是 $O(N^2)$ 的，还需要优化。
仔细观察可以发现，这个 $DP$ 方程中所有都是要 $+out_j$ 的，而所有的 $(f[j] + in_i)$ 也是只跟 $j$ 有关。如果按照外半径排序的话那么只需要求前缀最小值即可。使用线段树或者树状数组维护一下即可。
其实如果是按照内半径排序之后进行处理的话，访问到每个娃娃的时候外半径比它的内半径小的一定已经处理完了，可以直接开个数组按外半径大小来维护，由于内半径是有序的所以直接使用一个指针来维护应该就可以了。
但是因为有排序操作所以复杂度被限制在了 $O(N\log N)$ ，但是显然后一种做法会快不少。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
long long mod = 1e9 + 7;
long long inf = 0x3f3f3f3f3f3f3f3f;
long long n, m = 0;
struct ex {
long long x, y;
ex(){
x = inf, y = 0;
}
};
ex a[maxn];
int c[maxn];
int p[maxn];
map <int, int> s;
ex merge(ex x, ex y){
if(x.x < y.x){
return x;
}else if(x.x > y.x){
return y;
}else{
ex ret;
ret.x = x.x, ret.y = x.y + y.y;
if(ret.y > mod)ret.y -= mod;
return ret;
}
}
struct bt {
ex tree[maxn];
int lowbit(int x){
return x & -x;
}
ex sum(int p){
ex ret;
while(p){
ret = merge(ret, tree[p]);
p -= lowbit(p);
}
return ret;
}
int update(int p, ex x){
while(p <= n + 1){
tree[p] = merge(tree[p], x);
p += lowbit(p);
}
return 0;
}
} tree;
bool cmpa(ex x, ex y){
return x.x < y.x;
}
bool cmpb(int x, int y){
return a[x].y < a[y].y;
}
int main(){
int i, j;
ex ans;
long long x, y;
long long maxx = 0;
scanf("%d", &n);
for(i=1;i<=n;i++){
scanf("%lld%lld", &a[i].x, &a[i].y);
swap(a[i].x, a[i].y);
maxx = max(maxx, a[i].x);
c[i] = i;
}
sort(a + 1, a + n + 1, cmpa);
sort(c + 1, c + n + 1, cmpb);
for(i=1;i<=n;i++){
p[c[i]] = i;
if(!s.count(a[c[i]].y))s[a[c[i]].y] = i;
}
ex tmp;
tmp.x = 0, tmp.y = 1;
tree.update(1, tmp);
for(i=1;i<=n;i++){
x = s.upper_bound(a[i].x) -> second;
ex ret = tree.sum(x);
ret.x += a[i].x;
if(a[i].y > maxx){
ans = merge(ans, ret);
}
ret.x -= a[i].y;
tree.update(p[i] + 1, ret);
}
printf("%lld\n", ans.y);
return 0;
}