【NOIP2018模拟赛2018.10.22】pets

题目

题解

–emmm
首先判断是否合法就是判断是否存在环
拓扑排序搞定
然后就是dp算出k
f[i][j]：表示处理到1中i位置，2中j位置时的最大插入数
我们只需要预处理j是否可以插在i后面
就可以n^2转移了

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=1005;

int n,m,M;
int g[MAXN][MAXN],G[MAXN][MAXN];
int a[MAXN],b[MAXN];
int du[MAXN];
bool isu[MAXN],flag,ok[MAXN][MAXN];
int q_1[MAXN],l1,q_2[MAXN],l2;
int f[MAXN][MAXN];

void topsort_a(){
	memset(isu,0,sizeof(isu));
	queue<int>q;
	for(int i=1;i<=m;i++)
		if(!du[a[i]])
			q.push(a[i]);
	while(q.size()){
		int x=q.front();
		q.pop();
		isu[x]=1;
		q_1[++l1]=x;
		for(int i=1;i<=m;i++)
			if(G[x][a[i]]){
				G[x][a[i]]=0;
				du[a[i]]--;
				if(!du[a[i]])
					q.push(a[i]);
			}
	}
	if(l1<m)
		flag=1;
}

void topsort_b(){
	memset(isu,0,sizeof(isu));
	queue<int>q;
	for(int i=1;i<=M;i++)
		if(!du[b[i]])
			q.push(b[i]);
	while(q.size()){
		int x=q.front();
		q.pop();
		isu[x]=1;
		q_2[++l2]=x;
		for(int i=1;i<=M;i++)
			if(G[x][b[i]]){
				G[x][b[i]]=0;
				du[b[i]]--;
				if(!du[b[i]])
					q.push(b[i]);
			}
	}
	if(l2<M)
		flag=1;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			scanf("%d",&g[i][j]);
			G[i][j]=g[i][j];
		}
	for(int i=1;i<=m;i++){
		scanf("%d",&a[i]);
		isu[a[i]]=1;
	}
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
			if(g[a[i]][a[j]])
				du[a[j]]++;
	for(int i=1;i<=n;i++)
		if(!isu[i])
			b[++M]=i;
	for(int i=1;i<=M;i++)
		for(int j=1;j<=M;j++)
			if(g[b[i]][b[j]])
				du[b[j]]++;
	topsort_a();
	topsort_b();
	if(flag){
		cout<<"NO";
		return 0;
	}
	cout<<"YES ";
	for(int j=1;j<=l2;j++){
		int i=1;
		while(g[q_1[i]][q_2[j]])
			i++;
		flag=0;
		for(int k=i;k<=l1;k++)
			if(g[q_1[k]][q_2[j]]){
				flag=1;
				break;
			}
		if(!flag)
			ok[i-1][j]=1;
	}
	for(int i=0;i<=l1;i++){
		for(int j=0;j<=l2;j++){
			if(i)
				f[i][j]=max(f[i][j],f[i-1][j]);
			if(j)
				f[i][j]=max(f[i][j],f[i][j-1]);
			if(j&&ok[i][j])
				f[i][j]=max(f[i][j],f[i][j-1]+1);
		}
	}
	cout<<f[l1][l2];
	return 0;
}