正題

題面鏈接:https://www.ybtoj.com.cn/contest/62/problem/4

---

題目大意

$n$個(gè)區(qū)間，如果第$x$個(gè)區(qū)間和第$y$個(gè)區(qū)間有交集那么$x$到$y$直接就有一條邊。

求這張圖上的所有導(dǎo)出子圖中有多少棵樹(shù)。

---

解題思路

條件可以轉(zhuǎn)換為這些區(qū)間聯(lián)通并且沒(méi)有一個(gè)位置被$3$個(gè)區(qū)間同時(shí)覆蓋。

那么如果一個(gè)包含關(guān)系出現(xiàn)在這個(gè)圖里，那么被包含的那個(gè)一定是作為葉子的。所以可以按照左端點(diǎn)排序后考慮$dp$，設(shè)$f_{i,j}$表示到第$i$個(gè)區(qū)間作為父節(jié)點(diǎn)時(shí)右端點(diǎn)擴(kuò)展到的最遠(yuǎn)的位置。

那么有以下幾種轉(zhuǎn)移。

• 區(qū)間$i$直接開(kāi)一個(gè)新根節(jié)點(diǎn)
• 不選擇區(qū)間$i$
• 選擇$i$作為一個(gè)被包含在$[r_x+1,j]$這個(gè)范圍內(nèi)的區(qū)間，擴(kuò)展右端點(diǎn)
• 選擇$i$作為一個(gè)被包含在$[r_x+1,+\infty ]$的區(qū)間作為新的父節(jié)點(diǎn)

預(yù)處理一個(gè)$nex{t}_i$表示$i$往右擴(kuò)展到的第一個(gè)左端點(diǎn)的那個(gè)區(qū)間的即可$O(n^2)$轉(zhuǎn)移

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2100,L=4000,XJQ=1e9+7; struct node{int l,r; }a[N]; int n,nxt[N*2],f[N][N*2],ans; bool cmp(node x,node y) {return x.l<y.l;} int main() {freopen("graph.in","r",stdin);freopen("graph.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r);sort(a+1,a+1+n,cmp);int cnt=0;a[n+1].l=L+1; for(int i=1;i<=n+1;i++)while(cnt<L&&cnt<a[i].l)nxt[cnt++]=i-1;for(int i=1;i<=n;i++){(f[i][a[i].r]+=1)%=XJQ;for(int j=1;j<=L;j++){(f[i][j]+=f[i-1][j])%=XJQ;if(a[i].l>j)continue;if(a[i].r<=j)(f[nxt[a[i].r]][j]+=f[i-1][j])%=XJQ;if(a[i].r>j)(f[nxt[j]][a[i].r]+=f[i-1][j])%=XJQ;}}for(int i=1;i<=L;i++)(ans+=f[n][i])%=XJQ;printf("%d\n",ans); }

總結(jié)

以上是生活随笔為你收集整理的YbtOJ#20082-[NOIP2020模拟赛B组Day8]导出子图【dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。