非常有意思的 dp，很难想出来吧.
如果对着图去想，很难有思路，所以可以把图上的问题转化为序列问题.
我们发现，如果一个点集合法，当且仅当这个点集构成一个不降序列，且其他点都与这个点集形成逆序对.
令 $f[i]$ 表示由 $1$ ~ $i$ （选 $i$ ）构成的合法方案数.
然后如果不选一个元素，显然这个元素必须和距离该元素最近的被选元素形成逆序对.
假设我们求完 $f[i]$，要去更新 $j$ ($j>i$），则如果中间元素大于 $a[i]$，则中间元素必须大于 $a[j]$.
小于的情况同理（只要记住更新最大值位置就行）
#include <bits/stdc++.h>
#define N 1009
#define ll long long
#define mod 1000000007
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int val[N][N],f[N];
int main()
{
// setIO("input");
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y),val[x][y]=val[y][x]=1;
}
f[0]=1;
for(int i=0;i<=n;++i)
{
int tmp=0;
for(int j=i+1;j<=n+1;++j)
{
if((!tmp||val[tmp][j])&&!val[i][j])
(f[j]+=f[i])%=mod,tmp=j;
}
}
printf("%d\n",f[n+1]);
return 0;
}
原文：https://www.cnblogs.com/guangheli/p/13030336.html