NKOJ 3500 独立集（dp）

发表于 |
字数统计: 651字 | 阅读时长 ≈ 3min

P3500【2015多校联训6】独立集

问题描述
这里写图片描述

输入格式

输入包含两行，第一行为 N，
第二行为 1 到 N 的一个全排列

输出格式

输出包含两行，第一行输出最大独立集的大小，第二行从小到大输出一定在最大独立集 的点的编号。

样例输入

3
3 1 2

样例输出

2
2 3

提示

30%的数据满足 N<=16
60%的数据满足 N<=1,000
100%的数据满足 N<=100,000

仔细观察，发现第一问就是最长上升子序列，因为逆序对才会连边，那么没有边相连的点一定是正序的，那么问题就是求最长正序，即最长上升子序列。

考虑第二问，优秀的做法做不来，搞个暴力。
假设以$i$为结尾的最长上升子序列长度为$k$，那么将$A[i]$加到一个$set$，$P$中，将$i$加到另一个$set$,$Q$中，那么跑完最长上升子序列后，令第一问答案为$len$

从$len$开始倒着讨论，用$P[k],Q[k]$中最大的元素去删除$P[k-1],Q[k-1]$中的元素，删除条件就是如果$P[k-1],Q[k-1]$中的一个元素不能转移到$P[k],Q[k]$中的任一元素，那么删除。

如果讨论时发现某$set$中仅有一个元素，那么这个元素一定要选。复杂度$nlogn$

优秀做法参见THH

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#define N 100055
using namespace std;
set<int>Q[N],R[N];
int n,A[N],F[N],B[N],id[N],ans;
bool mark[N];
int main()
{
	set<int>::iterator x,y,z;
	int i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&A[i]),id[A[i]]=i;
	memset(B,60,sizeof(B));B[0]=0;Q[0].insert(0);
	for(i=1;i<=n;i++)
	{
		F[i]=lower_bound(B+1,B+n+1,A[i])-B;
		B[F[i]]=A[i];
		Q[F[i]].insert(A[i]);
		R[F[i]].insert(i);
		ans=max(ans,F[i]);
	}
	for(i=ans;i>=1;i--)
	{
		if(Q[i].size()==1)
		{
			x=Q[i].begin();
			mark[*x]=1;
		}
		x=Q[i].end();x--;
		y=Q[i-1].lower_bound(*x);
		for(z=y;z!=Q[i-1].end();z++)R[i-1].erase(R[i-1].find(id[*z]));
		Q[i-1].erase(y,Q[i-1].end());
		x=R[i].end();x--;
		y=R[i-1].lower_bound(*x);
		for(z=y;z!=R[i-1].end();z++)Q[i-1].erase(Q[i-1].find(A[*z]));
		R[i-1].erase(y,R[i-1].end());
	}
	printf("%d\n",ans);
	for(i=1;i<=n;i++)if(mark[i])printf("%d ",id[i]);
}