LIS.LCS.LCIS相关问题

文章目录

P1020 [NOIP1999 普及组] 导弹拦截
P1439 【模板】最长公共子序列
P1637 三元上升子序列
272. 最长公共上升子序列
LCIS
273. 分级
Sequence
P4597 序列 sequence

P1020 [NOIP1999 普及组] 导弹拦截

导弹拦截应该是接触DP的第一题（只不过洛谷上的数据加强了，按照上图的 $O(N^2)$ 做法过不去QAQ可以改用二分。

Dilworth定理：偏序集能划分成的最少的全序集个数等于最大反链的元素个数

把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度（LIS)

#include 
using namespace std;
int a[100010],LDS[100010],LIS[100010];
int main()
{
	int x,i=0,len=1;
	while(~scanf("%d",&x))
		a[i++]=x;
	LDS[0]=a[0];
	for(int j=1;j<i;j++)
	{
		if(a[j]<=LDS[len-1])
			LDS[len++]=a[j];
		else
		{
			int l=0,r=len;
			while(l<r)
			{
				int mid=(l+r)>>1;
				if(a[j]>LDS[mid]) r=mid;
				else l=mid+1;
			}
			LDS[l]=a[j];
		}
	}
	cout<<len<<endl;
    LIS[0]=a[0];
    int len2=1;
	for(int j=1;j<i;j++)
	{
		if(a[j]>LIS[len2-1])
			LIS[len2++]=a[j];
		else
		{
			int l=0,r=len2;
			while(l<r)
			{
				int mid=(l+r)>>1;
				if(a[j]<=LIS[mid]) r=mid;
				else l=mid+1;
			}
			LIS[l]=a[j];
		}
	}
	cout<<len2<<endl;
    return 0;
}
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
45
46
47

P1439 【模板】最长公共子序列

也不给你用上图的朴素DP过去( $O(N^2)$ ）www

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
     {
     	dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
     	if(a1[i]==a2[j])
     	dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
     }
   cout<<dp[n][m];
1
2
3
4
5
6
7
8

但本题数据有个明显的特征即两个序列都是全排列，也就是说我们可以重新构造一种映射关系。

#include 
using namespace std;
int a[100010],b[100010],LIS[100010];
int main()
{
	int n,i;
	cin>>n;
	//由于a b 中元素完全相同，只是顺序不同，可以利用映射关系，将a映射成一个单调递增序列 
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		a[x]=i;
	}
	//相应地，由a给出的映射关系，可将b构造成一个新的序列 
	for(int i=1;i<=n;i++)
	{
		int y;
		scanf("%d",&y);
		b[i]=a[y];
	}
	// 两个序列的子序列，一定是a的子序列。而a本身就是单调递增的。因此这个子序列是单调递增的。
	//换句话说，只要这个子序列在b中单调递增，它就是a的子序列
    //哪个最长呢？当然是b的LIS最长。下用二分+贪心求b的LIS即可 
	LIS[1]=b[1];
    int len2=1;
	for(int j=2;j<=n;j++)
	{
		if(b[j]>LIS[len2])
			LIS[++len2]=b[j];//如果此时检索到的数比LIS的最后一个数（也即最大的数）大，直接插到LIS尾部 
		else//否则，在LIS前面的数中二分查找合适的位置进行替换 
		{
			int l=1,r=len2;
			while(l<r)
			{
				int mid=(l+r)>>1;
				if(b[j]<=LIS[mid]) r=mid;
				else l=mid+1;
			}
			LIS[l]=b[j];
		}
	}
	cout<<len2<<endl;
    return 0;
}
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
45

P1637 三元上升子序列

P1637 三元上升子序列
 UVA12983 The Battle of Chibi

给定一个长度为n的序列，求其包含的m元单调上升子序列个数。
见求LIS思DP。导弹拦截那种题，开f[结尾编号]=序列长度，信息量不够，考虑定义f[序列长度][结尾编号] =序列个数。

状态转移： $f[i][j]=\sum f[i-1][k],1<=kf[i][j]=∑f[i−1][k],1<=k<j,a[k]<a[i]$

这样做的时间复杂度为 $O(n^2*m)$

得想办法在更短时间内统计出 $\sum f[i-1][k]$ ,树状数组或者线段树都可以实现在 $O (l o g n)$ 内的区间统计。

先离散化，将a[]的分布集中起来，以a[k]为下标储存f[i-1][k]的值。

此时针对状态转移方程写两层循环：外层循环枚举长度，每次枚举到一个长度都重置一下树状数组c[]。{内层枚举序列结尾坐标，此前已将f[i-1][k]增加到树状数组中，此时只需用树状数求和即可。然后把f[i-1][j]加到树状数组中，这个值只会更新到比a[j]大的数（对应状态转移方程里的a[k]

#include
using namespace std;
#define ll long long
const int N=30010;
ll n,f[4][N],a[N],b[N],c[N],ans;

ll lowbit(ll x) { return x&(-x);}

void update(ll p,ll v)
{
	for(int i=p;i<=n;i+=lowbit(i))
		c[i]+=v;
} 

ll ask(int p)
{
	ll sum=0;
	for(int i=p;i;i-=lowbit(i))
		sum+=c[i];
	return sum;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	unique(b+1,b+n+1)-(b+1);
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(b+1,b+n+1,a[i])-b;//二分查找在数组中的位置
		f[1][i]=1;//初始化：长度唯一，本身为结尾
	}
	//离散化结束，初始化结束，准备工作完成
	for(int i=2;i<=3;i++)//枚举长度
	{
		memset(c,0,sizeof(c));//重置树状数组
		for(int j=1;j<=n;j++)
		{
			f[i][j]=ask(a[j]-1);//求和
			update(a[j],f[i-1][j]);//更新
		}
	}
	for(int i=1;i<=n;i++)
		ans+=f[3][i];
	cout<<ans; 
    return 0;
}


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
45
46
47
48
49
50
51

272. 最长公共上升子序列

是LIS和LCS的结合体，可以尝试用a解决公共子序列问题，用b解决上升子序列问题。
定义 $f [i] [j]$ : $a [1] - a [i], b [1] - b [j]$ 可以构成的以 $b [j]$ 结尾的LCIS的长度。

if(A[i]==B[j]) F[i,j]=F[i-1,j];
if(A[i]!=B[j],F[i,j]=max{F[i-1,k]}+1;(0<=k<j)
1
2

未优化前，
考虑当a[i]==b[j]时，上一步从b[1]~b[j]中的某一个b[k]转化而来。

#include
using namespace std;
const int N=3010;
int f[N][N];
int n,a[N],b[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            f[i][j]=f[i-1][j];
            if(a[i]==b[j])
            {
               int maxv=1;
                for (int k=1;k<j;k++)
                    if (a[i]>b[k]) maxv=max(maxv, f[i - 1][k] + 1);
                f[i][j]=max(f[i][j], maxv);
            }
        }
    int ans=0;
    for(int j=1;j<=n;j++)
        ans=max(ans,f[n][j]);
    cout<<ans<<endl;
    return 0;
}
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

TLE了，发现可以没必要枚举k，可以用val实时更新前缀的max长度。

#include
using namespace std;
const int N=3010;
int f[N][N];//a1~ai,b1~bj可以构成的以bj结尾的LCIS的长度
int n,a[N],b[N],ans=0,m;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
    {
        int val=0;//(i,0)的LCIS长度
        //i固定，b1->bn时LCIS长度一定是单调递增的
        for(int j=1;j<=n;j++)
        {
            if(a[i]==b[j]) f[i][j]=val+1;//遍历到一个ai、bj相同的位置，长度++
            else f[i][j]=f[i-1][j];//不相等，直接继承(i-1,j)的长度
            if(b[j]<a[i]) val=max(val,f[i-1][j]);//更新val:(i,j)前面的LCIS长度
            //另一种情况：(b[j]>a[i])一定不会影响到LCIS的长度
        }
    }
    for(int j=1;j<=n;j++)//找出所有以bj结尾的LCIS中长度最大的
        ans=max(ans,f[n][j]);
    cout<<ans<<endl;
    return 0;
}
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

进一步发现f的第一维也是可以省略的。

#include
using namespace std;
const int N=3010;
int f[N];//a1~ai,b1~bj可以构成的以bj结尾的LCIS的长度
int n,a[N],b[N],ans=0,m;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
    {
        int val=0;//(i,0)的LCIS长度
        //i固定，b1->bn时LCIS长度一定是单调递增的
        for(int j=1;j<=n;j++)
        {
            if(a[i]==b[j]) f[j]=val+1;//遍历到一个ai、bj相同的位置，长度++
            if(b[j]<a[i]) val=max(val,f[j]);//更新val:(i,j)前面的LCIS长度
            //另一种情况：(b[j]>a[i])一定不会影响到LCIS的长度
        }
    }
    for(int j=1;j<=n;j++)//找出所有以bj结尾的LCIS中长度最大的
        ans=max(ans,f[j]);
    cout<<ans<<endl;
    return 0;
}
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

LCIS

加上路径输出，scheme保存前一个位置。

#include
using namespace std;
const int N=3010;
int f[N];//a1~ai,b1~bj可以构成的以bj结尾的LCIS的长度
int n,a[N],b[N],ans[N],m,scheme[N],p;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    cin>>m;
    for(int i=1;i<=m;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
    {
		int id=0;
        //i固定，b1->bn时LCIS长度一定是单调递增的
        for(int j=1;j<=m;j++)
        {
            if(a[i]==b[j]) f[j]=f[id]+1,scheme[j]=id;
			//遍历到一个ai、bj相同的位置，长度++,记录下j前面一个位置是id 
            if(b[j]<a[i]&&f[id]<f[j]) id=j;
        }
    }
    int p=0;
    for(int i=1;i<=m;i++)
        if(f[i]>f[p]) p=i;//找出所有以bj结尾的LCIS中长度最大的
    printf("%d\n",f[p]);
    int top=0;
    while(f[p]--) 
	{
        ans[++top]=b[p];
        id=scheme[p];//从后往前倒出来 
    }
    for(int i=top;i;i--)
        printf("%d ",ans[i]);//输出方案前需要记录
    return 0;
}
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

273. 分级

即将一个序列转化成非严格单调递增（或者递减）序列的最小代价。
引理：在满足ans最小的情况下，一定存在一种构造序列b的方法，使得b中的数值都在a中出现过。

状态转移：F[i,j]=min{F[i-1,k]}+|A[i]-j|;(0<=k<j)
1

像LCIS那题所述，优化枚举k的一维。

#include
using namespace std;
typedef long long LL;
const int N=2020;
LL a[N],b[N],f[N][N];
//f[i][j]表示已经考虑前a[i]个且最后一个以b[j]结尾的最优解
LL ans=1e18;
int n;

void work()
{
    for(int i=1;i<=n;i++)
    {
        LL temp=1e18;
        for(int j=1;j<=n;j++)
        {
            temp=min(temp,f[i-1][j]);//对前缀取最小
            f[i][j]=temp+abs(a[i]-b[j]);
        }
    }
    for(int j=1;j<=n;j++)
        ans=min(ans,f[n][j]);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),b[i]=a[i];
     //引理：在满足ans最小的情况下，一定存在一种构造序列b的方法，使得b中的数值都在a中出现过
    sort(b+1,b+n+1);work();//b[i]单调递增的情况下取一遍答案
    reverse(b+1,b+n+1);work();//b[i]单调递减的情况下取一遍答案
    cout<<ans<<endl;
    return 0;
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

Sequence

比起上一题会卡空间，要优化一维。

#include
using namespace std;
typedef long long LL;
const int N=5050;
LL a[N],b[N],f[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]),b[i]=a[i];
     //引理：在满足ans最小的情况下，一定存在一种构造序列b的方法，使得b中的数值都在a中出现过
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            f[j]+=abs(b[j]-a[i]);
			if(j>1)	f[j]=min(f[j],f[j-1]);
        }
    }
    cout<<f[n];
    return 0;
}
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

P4597 序列 sequence

卡 $O(N^2)$ 的时间复杂度啦，要用堆优化。

#include
using namespace std;
typedef long long LL;
LL n,ans,x;
priority_queue<LL>q;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	scanf("%lld",&x);
    	q.push(x);
        if(q.top()>x)
		{
            ans+=q.top()-x;
            q.pop();
            q.push(x);
        }
    }
    cout<<ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

P.S.
Q：把一个序列变成非严格单调递增的，至少需要修改几个数？ A：序列A的总长度减去A的最长不下降子序列长度。
Q：把一个序列A变成严格单调递增的，至少需要修改几个数？ A：构造序列 $B [i] = A [i] - i$ ,答案为序列总长度减去B的最长不下降子序列长度。

相关阅读:
Algorithm Review 5
一起学习集合框架之 TreeSet
TensorFlow是什么
如何利用DGL官方库中的rgcn链接预测代码跑自己的数据集（如何在DGL库的链接预测数据集模块定义自己的数据集类）
vue项目中将html转为pdf并下载
JVM内存参数配置
索引的创建和设计原则
2023年天津仁爱学院高职升本科专业考试报考须知
springCloud-Nacos注册中心的搭建
Java修仙之基础功法篇-＞构建者模式

原文地址：https://blog.csdn.net/m0_60630928/article/details/127866322