[文章目录]
Description
我们令a[i]表示看守的第i扇门对应囚犯的哪一扇门。令图G为有n个节点的图，编号为1～n。对于满足1≤i< j≤n的一对i和j，如果有a[i]>a[j]，那么在G中编号为i和j的节点之间连一条边。得到的图G被称为逆序图。对于图G=(V,E)，非空点集S∈V是一个独立集当且仅当对于任意两个点u,v∈V，不存在(u,v)∈E。而S是一个覆盖集当且仅当对于任意点v?S存在点u∈S满足(u,v)∈E。我们在意的是，图G中有多少个点集既是独立集又是覆盖集。出于某种不知名的原因，被迫参加监狱游戏的大家的安危和这个问题的答案有关。拜托了，请一定要求出这个方案数。n≤1000，0≤m≤(n(n-1))/2
CQzhangyu讲的这道题目。膜拜加RP。
思路：如果这个图不存在上述的构成，这个问题据大师说是无解的。这种构图一定有一些性质。发现可以在n^2的时间还原a[]数组，那么点独立集纪委这个序列是单调递增的，加上点覆盖集，那么这个序列就是极长上升子序列。那么DP求出机场上升子序列的个数，然后挑选那些右边没有比起大的结尾的极长上升子序列更新答案。时间复杂度O(n^2)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod=1000000007;
int n,m,ans,a[1100],cd[1100],dp[1100];
int head[1100],to[2100000],nxt[2100000],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}
bool v[1100];
int find(int x)
{
for(int i=1;i<=n;++i)
{
x-=!v[i];
if(x==-1) return v[i]=1,i;
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m); int x,y;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
add(x,y); cd[min(x,y)]++;
}
for(int i=1;i<=n;++i) a[i]=find(cd[i]);
a[0]=-1; dp[0]=1; int mi=-2;
for(int i=1;i<=n;++i,mi=-2)
for(int j=i-1;~j;--j) if(a[j]<a[i]&&a[j]>mi)
dp[i]=(dp[i]+dp[j])%mod,mi=a[j];
int mx=-1;
for(int i=n;i;--i) if(mx<a[i])
ans=(ans+dp[i])%mod, mx=a[i];
printf("%d",ans);
return 0;
}