20200718 SCOI模拟T3（dp）

T1 囚人的旋律

思路：
一般图的独立集问题是 NP 问题，所以肯定转换成序列做

考虑怎么转换成序列
序列上连边的两点为逆序对
对于图上一点 u，与它相连的点中比它大的点有 k 个，所以序列的位置 u 后有 k 个位置的值比 val[u] 大
从序列开头枚举到结尾，对于每一个位置统计后面比它大的数的个数
它就是剩下的数中的第 k+1 大的数
时间复杂度：$O(n^2)$O(n2)

考虑满足独立集
集合中任意两点未连边，所以集合中的点不存在逆序对，所以选出的序列单调上升

考虑满足覆盖集
对于任意不在集合中的一点，存在一点与之连边，且在集合中
在序列上选的点将序列分段，设一段的左端点为 l，右端点为 r
对于 $l-r$l−r 中任意一点 u，肯定与 $l或r$l或r 成逆序对，有 $u<l或者u>r$u<l或者u>r

于是可以 dp，转移方程为：
$f[i]=\sum_{j=1}^{i-1} f[满足条件的j]$f[i]=j=1∑i−1​f[满足条件的j]
枚举 i，j，暴力验证，时间复杂度：$O(n^3)$O(n3)
考虑优化
从左到右枚举每个位置，枚举每个它可以转移到的位置，维护大于左端点的最小值
时间复杂度：$O(n^2)$O(n2)

代码：

#include <bits/stdc++.h>
using namespace std;
#define re register
namespace IO {
inline char ch() {
  static char buf[1 << 21], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int in() {
  int s = 0, f = 1;
  char x;
  for (x = ch(); x < '0' || x > '9'; x = ch())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = ch()) s = (s * 10) + (x & 15);
  return f == 1 ? s : -s;
}
}  // namespace IO
using namespace IO;

const int A = 5e5 + 5;
const int mod = 1e9 + 7;
const int INF = 1e9;
int n, m;
int head[A], tot_road;
struct Road {
  int nex, to;
} road[2 * A];
inline void edge(int x, int y) {
  road[++tot_road] = {head[x], y};
  head[x] = tot_road;
}
int ex[A];
int val[A];
int f[A];

inline void build() {
  for (int i = 1; i <= n; i++) {
    int num = 0;
    for (int y = head[i]; y; y = road[y].nex) {
      int z = road[y].to;
      if (z > i) num++;
    }
    for (int j = 1; j <= n; j++) {
      if (!ex[j]) num--;
      if (num == -1) {
        val[i] = j;
        ex[j] = 1;
        break;
      }
    }
  }
  return;
}

// inline void DP(){
//   f[0]=1;
//   for(int i=1;i<=n+1;i++){
//     for(int j=0;j<i;j++){
//       if(val[j]>val[i]) continue;
//       int pos=0;
//       for(int k=j+1;k<i;k++){
//         if(val[k]>val[j]&&val[k]<val[i]){
//           pos=1;
//           break;
//         }
//       }
//       if(pos) continue;
//       f[i]=(f[i]+f[j])%mod;
//     }
//   }
//   return;
// }
// n^3

inline void DP() {
  f[0] = 1;
  for (int i = 0; i <= n; i++) {
    int minn = INF;
    for (int j = i + 1; j <= n+1; j++) {
      if (val[j] > val[i] && minn > val[j]) f[j] = (f[j] + f[i]) % mod;
      if (val[j] > val[i]) minn = min(minn, val[j]);
    }
  }
  return;
}
//n^2

signed main() {
  // freopen("senritsu.in", "r", stdin);
  // freopen("senritsu.out", "w", stdout);
  n = in(), m = in();
  for (int i = 1; i <= m; i++) {
    int u = in(), v = in();
    edge(u, v), edge(v, u);
  }
  build();
  val[0] = 0, val[n + 1] = n+1;
  DP();
  printf("%d\n", f[n + 1]);
  puts("");
  return 0;
}
/*
5 5
2 4
2 5
1 4
3 4
3 5
*/