TYVJ1071 LCIS 线性DP+决策集优化

问题描述

TYVJ1071

---

题解

暴力\(\mathrm{DP}\)

首先，一个\(O(n^3)\)的解法：

设\(opt_{i,j}\)代表\(a\)的前\(i\)个和\(b\)的前\(j\)个的\(\mathrm{LCIS}\).

显然有：

1.\(a_i=b_j\)

\[opt_{i,j}=opt_{i-1,j}
\]

2.\(a_i≠b_j\)

\[opt_{i,j}=max_{0 \le k < j,b_k<a_i} {opt_{i-1,k}}+1
\]

于是得到代码：

#include<bits/stdc++.h>

using namespace std;

void read(int &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

	if(ch=='-') ch=getchar(),fh=-1;

	else fh=1;

	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

const int maxn=3007;

int n;

int a[maxn],b[maxn],opt[maxn][maxn];

int ans;

int main(){

	read(n);

	for(int i=1;i<=n;i++) read(a[i]);

	for(int i=1;i<=n;i++) read(b[i]);

//	opt[0][0]=1;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=n;j++){

			if(a[i]!=b[j]) {opt[i][j]=opt[i-1][j];continue;}

			for(int k=0;k<j;k++) if(b[k]<a[i]) opt[i][j]=max(opt[i][j],opt[i-1][k]+1);

		}

	}

	for(int i=1;i<=n;i++) ans=max(opt[n][i],ans);

	printf("%d\n",ans);

	return 0;

}

这数据怎么这么水啊，怎么\(O(n^3)\)过\(3000\)啊。

决策集优化

发现这道题的\(\mathrm{DP}\)转移过程，已经在决策集中的决策点一定不会再出去，换而言之，这道题\(\mathrm{DP}\)的决策集是不断增大的。

于是考虑用一个变量\(val\)记录决策集中的最值，即可实现复杂度\(O(n^2)\)。

Code by lydrainbowcoat

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 3006;

int n, a[N], b[N], f[N][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++) {

		int val = 0;

		for (int j = 1; j <= n; j++) {

			f[i][j] = (a[i] == b[j] ? val + 1 : f[i-1][j]);

			if (b[j] < a[i]) val = max(val, f[i-1][j]);

		}

	}

	int ans = 0;

	for (int j = 1; j <= n; j++) ans = max(ans, f[n][j]);

	cout << ans << endl;

	return 0;

}

总结——《算法竞赛进阶指南》

这道题的转移部分的优化告诉我们，在实现状态转移方程时，要注意观察决策集合的范围随着状态的变化情况。对于“决策集合中的预算只增多不减少”的情景，就可以像本题一样维护一个变量来记录决策集合的当前信息，避免重复扫描，把转移的复杂度降低一个量级。