【洛谷P1983】车站分级

车站分级

首先，可以发现火车停靠站点的大小是没有什么规律的，

火车可以停靠在级别<=当前级别的站点，必须停靠在级别>=当前最高级别的站点

但是所有没有被停靠的站点级别一定比所有被停靠了的站点级别低

于是就可以据此建一个DAG，拓扑排序或记搜即可

（O(n^3)建图居然过了）

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<bitset>
 5 using namespace std;
 6 #define rep(i,l,r) for(int i=l;i<=r;i++)
 7 #define reset(a) fill(a,a+n+1,0)
 8 #define N 1010
 9 int n,m,Head[N],num,a[N],tot,f[N],ans;
10 bitset<N> line[N];
11 struct NODE{
12     int to,next;
13 } e[10000010];
14 bool vis[N];
15 inline int read(){
16     int x=0; char c=getchar();
17     while(c<'0'||c>'9') c=getchar();
18     while('0'<=c&&c<='9') { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }
19     return x;
20 }
21 inline void add(int x ,int y){
22     e[++num].to=y;
23     e[num].next=Head[x];
24     Head[x]=num;
25 }
26 int dfs(int t){
27     if(f[t]) return f[t];
28     for(int i=Head[t];i;i=e[i].next)
29      f[t]=max(f[t],dfs(e[i].to));
30     return ++f[t];
31 }
32 int main()
33 {
34     scanf("%d%d",&n,&m);
35     int x,y;
36     rep(i,1,m){
37         tot=0;
38         reset(vis); reset(a);
39         x=read();
40         while(x--){
41             a[++tot]=read();
42             vis[a[tot]]=1;
43         }
44         rep(j,a[1],a[tot]) if(!vis[j])
45          rep(k,1,tot) if(!line[j][a[k]])
46           { add(j,a[k]); line[j][a[k]]=1; }
47     }
48     for(int i=1;i<=n;i++){
49         if(!f[i]) dfs(i);
50         ans=max(ans,f[i]);
51     }
52     printf("%d
",ans);
53     return 0;
54 }