考场上一直在想怎么建图…结果发现可以Dp
给你 n n n 个套娃,每个套娃有两个参数 o u t i out_i outi, i n i in_i ini分别代表外表大小和内部体积两个套娃能够嵌套只有 o u t i < = i n j out_i<=in_j outi<=inj 满足,定义一组嵌套的套娃浪费空间为 i n i 1 + ( i n i 2 − o u t i 1 ) + ( i n i 3 − o u t i 2 ) + ⋯ + ( i n i k − o u t i k − 1 ) in_{i_1}+(in_{i_2}−out_{i_1})+(in_{i_3}−out_{i_2})+⋯+(in_{i_k}−out_{i_{k-1}}) ini1+(ini2−outi1)+(ini3−outi2)+⋯+(inik−outik−1)，求当浪费空间最小时的方案数，方案数模 1 0 9 + 7 10^9+7 109+7 数据范围： 1 ≤ n ≤ 2 ⋅ 1 0 5 ， 1 ≤ i n i < o u t i ≤ 1 0 9 1\le n\le 2⋅10^5，1\le in_i<out_i\le 10^9 1≤n≤2⋅105，1≤ini<outi≤109
我们可以发现其实可以抽象成一个 D A G DAG DAG图，就是求路径最短的方案数 我们将所有套娃按照 i n in in 为第一关键字, o u t out out 为第二关键字从小到大排序，然后从右至左枚举套娃,根据它的 o u t out out 二分出能容纳它的套娃最小下标 j j j，那么 [ j , n ] [j,n] [j,n] 套娃都可以容纳。我们考虑 D p Dp Dp f [ i ] f[i] f[i]:后 n − i n-i n−i 号套娃， i i i 号在最内时的最小浪费空间以及方案数 于是有状态转移方程式： f [ i ] = m i n o u t i < = i n j ( f [ j ] + i n i − o u t i ) = m i n o u t i < = i n j ( f [ j ] ) + i n i − o u t i f[i]=min_{out_i<=in_j}(f[j]+in_i-out_i)=min_{out_i<=in_j}(f[j])+in_i-out_i f[i]=minouti<=inj(f[j]+ini−outi)=minouti<=inj(f[j])+ini−outi 于是可以将 f [ j ] f[j] f[j] 用线段树维护,储存后面的最小值和方案数
利用线段树进行 D p Dp Dp 转移,之前听说过，现在写过了
#pragma G++ optimize (2) #include<set> #include<map> #include<stack> #include<cmath> #include<queue> #include<deque> #include<cstdio> #include<ctime> #include<bitset> #include<vector> #include<climits> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define LL long long #define ULL unsigned long long int read(){ int f=1,x=0;char c=getchar(); while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();} while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return f*x; } #define lch (i<<1) #define rch (i<<1|1) #define MAXN 200000 #define INF 0x3f3f3f3f #define Mod int(1e9+7) #define pii pair<int,int>//值,方案数 struct node{ int out,in; friend bool operator < (node a,node b){return a.in<b.in;} }toy[MAXN+5]; bool cmp(node a,node b){ if(a.in!=b.in) return a.in<b.in; return a.out<b.out; } inline int Add(int x,int y){ x+=y; if(x>=Mod) x-=Mod; return x; } pii Combine(pii a,pii b){ if(a.first!=b.first) return a.first<b.first?a:b; return pii(a.first,Add(a.second,b.second)); } pii tree[MAXN*5+5]; void Insert(int i,int L,int R,int p,pii x){ if(L==R){ tree[i]=x; return ; } int Mid=(L+R)>>1; if(p<=Mid) Insert(lch,L,Mid,p,x); if(Mid+1<=p) Insert(rch,Mid+1,R,p,x); tree[i]=Combine(tree[lch],tree[rch]); return ; } pii Query(int i,int L,int R,int l,int r){ if(l<=L&&R<=r) return tree[i]; int Mid=(L+R)>>1; pii ret(INF,0); if(l<=Mid) ret=Combine(ret,Query(lch,L,Mid,l,r)); if(Mid+1<=r) ret=Combine(ret,Query(rch,Mid+1,R,l,r)); return ret; } int main(){ int n=read(); for(int i=1;i<=n;i++){ int x=read(),y=read(); toy[i]=(node){x,y}; } sort(toy+1,toy+n+1); /* puts(""); for(int i=1;i<=n;i++) cout<<toy[i].out<<' '<<toy[i].in<<endl; */ for(int i=n;i>=1;i--){ int pos=lower_bound(toy+1,toy+n+1,(node){0,toy[i].out},cmp)-toy; if(pos>n){ Insert(1,1,n,i,pii(toy[i].in,1)); continue; } pair<int,int> p=Query(1,1,n,pos,n); Insert(1,1,n,i,pii(p.first+toy[i].in-toy[i].out,p.second)); } printf("%d\n",Query(1,1,n,1,n).second); return 0; }