P5871 [SEERC2018] Inversion 题解
题面：独立集中的点一定单调递增，支配集外的点不想入集必须保证能与支配集中的每个点都产生逆序对。所以独立支配集就是一个不可扩展的严格上升子序列（可扩展元素会被独立集性质强行拉拢）。
所以翻译一下题面，就是根据逆序对还原原序列，并且统计原序列中不可扩展的严格上升子序列的个数。显然用dp。
1.还原原序列，n^2暴力扫，很好理解。
void huanyuan (int n,int m){
int x, y;
for(int i = 1; i <= m;i++){
scanf("%d%d", &x, &y);
in[min(x, y)]++;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(!vis[j]){
if(in[i]) in[i]--;
else{
vis[j] = 1;
a[i] = j;
break;
}
}
}
}
}
还有一种方法，O(n)的，自己猜的，没有看到其它题解提到这种方法，但是是对的。
我也不知道怎么解释正确性。
void huanyuan(int n,int m){
register int x, y;
for(register int i = 1; i <= m;++i){
cin>>x>>y;
++in[min(x, y)],--in[max(x,y)];
}
for(register int i = 1; i <= n; ++i){
a[i]=i+in[i];
in[i]=0;//注意要初始化in数组，后面要用
}
}
2. 统计原序列中不可扩展的严格上升子序列的个数,n^2复杂度。
方便理解可以手模样例。
以样例三为例：
a[i]: 2 4 1 5 7 6 3
dp[i]: 1 1 1 2 2 2 2
in[ i ]: 1 1 1 1 0 0 0
long long solve(){//dp求出无法扩展的单调递增子序列的个数
for(register int i=1;i<=n;++i){
register int Max=0;
for(register int j=i-1;j>=1;--j){
if(a[i]>a[j]&&a[j]>Max){//如果当前a[j]<max肯定被max的数更新过了
Max=a[j];
dp[i]+=dp[j];
in[j]=1;
}
}
if(!dp[i])
dp[i]=1;
}
ans=0;
for(register int i=1;i<=n;++i){
//if(!in[i])
register bool k=in[i]==0;
ans+=dp[i]*k; //只累加没有被转移过的dp[i]
}
return ans;
}
3. AC代码
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000010],in[1000010],vis[1000010];
long long ans,dp[1000010];void huanyuan(int n,int m){
register int x, y;
for(register int i = 1; i <= m;++i){
cin>>x>>y;
++in[min(x, y)],--in[max(x,y)];
}
for(register int i = 1; i <= n; ++i){
a[i]=i+in[i];
in[i]=0;
}
}long long solve(){
for(register int i=1;i<=n;++i){
int Max=0;
for(register int j=i-1;j>=1;--j){
if(a[i]>a[j]&&a[j]>Max){
Max=a[j];
dp[i]+=dp[j];
++in[j];
}
}
if(!dp[i])
dp[i]=1;
}
ans=0;
for(register int i=1;i<=n;++i){
//if(!in[i])
register bool k=in[i]==0;
ans+=dp[i]*k;
}
return ans;
}int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin>>n>>m;
huanyuan(n,m);
cout<<solve();
return 0;
}
p.s.由于本题数据水的离谱，数组开到1e2就能过。
本蒟蒻第一次写题解，还请各位龘佬能提提意见。
避雷区：1.加了cin加速后用scanf会爆0；
2.初始化（比如我代码中的in数组在第二个还原算法中需要初始化，优化算法的时候出现的问题）
