SEERC 2018 I. Inversion
题目链接
http://codeforces.com/gym/101964/problem/I
题目大意
用一个 $1$ 到 $n$ 的一个数列的一个排列来构图。在数列中所有的逆序对的点对中建边。现在给你这个图的所有边，问你一共有多少种点的集合，使得这个集合中任意两个点都没有边相连，且其余所有点都最少与这个集合中的一个点相连。
题目分析
根据题目的提示，考虑可能需要将图还原成数列进行分析。我们考虑从这个数列中选出若干个点作为这个集合，那么这个集合应具备以下几个性质：
- 这若干个数应该是升序排列的，否则会出现逆序对出现连边。
- 对于这些数的右边的所有的点，应当都比选出来的最大的数（选出来的数的最后一个数）要小，这样才会出现逆序对，与点集有连边。
- 对于其他的不属于这个集合的点，应当不存在一个点，使得加入这个点后，这个选出来的数所组成的数列仍保持升序。因为如此的话应当是不存在逆序对的。
根据这性质 $1, 3$，可以进行 $DP$，计算出以每个点结尾的满足条件的升序数列有多少种情况，之后用性质 $2$ 进行校验即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 100 + 5;
int n, m;
int cnt[maxn];
int a[maxn];
long long f[maxn];
int maxx[maxn];
int read(){
int x;
scanf("%d", &x);
return x;
}
int main(){
int i, j;
int x, y;
long long ans = 0;
n = read();
m = read();
for(i=1;i<=m;i++){
x = read();
y = read();
cnt[max(x, y)]++;
}
for(i=n;i>0;i--){
int t = 0;
for(j=n;j>0;j--){
if(!a[j]){
if(t == cnt[i]){
a[j] = i;
break;
}else{
t++;
}
}
}
}
for(i=n;i>=1;i--){
maxx[i] = max(maxx[i + 1], a[i]);
}
f[0] = 1;
for(i=1;i<=n;i++){
int t = 0;
for(j=i-1;j>=1;j--){
if(a[j] < a[i]){
t = max(t, a[j]);
if(a[j] >= t){
f[i] += f[j];
}
}
}
if(f[i] == 0){
f[i] = 1;
}
}
for(i=1;i<=n;i++){
if(a[i] > maxx[i + 1]){
ans += f[i];
}
}
printf("%lld\n", ans);
return 0;
}