题解：P5871 [SEERC 2018] Inversion

· · 题解

题目大意

定义一个长为 n 的排列为一个序列 p_1, p_2, \dots, p_n，其中 [1, n] 范围内的整数都恰好在这个序列中出现一次。定义排列中的一个逆序对为一对整数 (i, j)，其中 i, j \in [1,n]，且满足 i<j, p_i>p_j。

定义一个逆序对图为一个有 n 个点的图，图中存在一条 (i, j) 的边当且仅当 (i,j) 是一个逆序对。

定义一个图中的独立集为一个图中点的集合，满足集合中的点两两之间没有边相连。定义一个图中的支配集为一个图中点的集合，满足不在这个集合中的点都与集合中的某个点有边相连。定义一个图中的独立支配集为一个图中点的集合，这个集合既是独立集又是支配集。

给定某一个长为 n 的排列的逆序对图，请计算出这个图中独立支配集的数量。

几乎就是复述一遍罢了

解题思路

先求出 cnt_i 的值后进行下一步。

然后考虑 dp，可得转移方程式 if(cnt[j]>maxn&&cnt[j]<cnt[i]) maxn=cnt[j],dp[i]+=dp[j];，接下去就是枚举每个求得的值然后比较并累加求和即可。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=110;
int a[N],cd[N],rd[N],cnt[N],dp[N];
vector<int>G[N<<1];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        if(u>v) swap(u,v);
        G[u].push_back(v);
        cd[u]++,rd[v]++;
    }
    for(int i=1;i<=n;i++) rd[i]=i-rd[i],cnt[i]=rd[i]+cd[i];
    for(int i=1;i<=n;i++){
        int maxn=0;
        for(int j=i-1;j>=1;j--){
            if(cnt[j]>maxn&&cnt[j]<cnt[i]) maxn=cnt[j],dp[i]+=dp[j];
        }
        if(dp[i]==0) dp[i]++;
    }
    int maxn=0,ans=0;
    for(int i=n;i>=1;i--) if(cnt[i]>maxn) maxn=cnt[i],ans+=dp[i];
    cout<<ans;
    return 0;
}