LIS LCS LCIS相关问题
P1020 [NOIP1999 普及组] 导弹拦截
导弹拦截应该是接触DP的第一题（只不过洛谷上的数据加强了，按照上图的$O(N^2)$做法过不去QAQ可以改用二分。
Dilworth定理：偏序集能划分成的最少的全序集个数等于最大反链的元素个数
把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度（LIS)
1 |
|
P1439 【模板】最长公共子序列
也不给你用上图的朴素DP过去($O(N^2)$）www
1 | for(int i=1;i<=n;i++) |
但本题数据有个明显的特征即两个序列都是全排列，也就是说我们可以重新构造一种映射关系。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
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;
}
P1637 三元上升子序列
P1637 三元上升子序列
UVA12983 The Battle of Chibi
给定一个长度为n的序列，求其包含的m元单调上升子序列个数。
见求LIS思DP。导弹拦截那种题，开f[结尾编号]=序列长度，信息量不够，考虑定义f[序列长度][结尾编号] =序列个数。
状态转移：$f[i][j]=\sum f[i-1][k],1<=k<j,a[k]<a[i]$
这样做的时间复杂度为$O(n^2*m)$
得想办法在更短时间内统计出$\sum f[i-1][k]$,树状数组或者线段树都可以实现在$O(log n)$内的区间统计。
先离散化，将a[]的分布集中起来，以a[k]为下标储存f[i-1][k]的值。
此时针对状态转移方程写两层循环：外层循环枚举长度，每次枚举到一个长度都重置一下树状数组c[]。{内层枚举序列结尾坐标，此前已将f[i-1][k]增加到树状数组中，此时只需用树状数求和即可。然后把f[i-1][j]加到树状数组中，这个值只会更新到比a[j]大的数（对应状态转移方程里的a[k]<a[i]），这些数后续会被调用（对应状态转移方程里的1<=k<j）}。
1 |
|
272. 最长公共上升子序列
是LIS和LCS的结合体，可以尝试用a解决公共子序列问题，用b解决上升子序列问题。
定义$f[i][j]$:$a[1]-a[i],b[1]-b[j]$可以构成的以$b[j]$结尾的LCIS的长度。
1 | if(A[i]==B[j]) F[i,j]=F[i-1,j]; |
未优化前，
考虑当a[i]==b[j]时，上一步从b[1]~b[j]中的某一个b[k]转化而来。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
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;
}
TLE了，发现可以没必要枚举k，可以用val实时更新前缀的max长度。
1 |
|
进一步发现f的第一维也是可以省略的。
1 |
|
LCIS
加上路径输出，scheme保存前一个位置。
1 |
|
273. 分级
即将一个序列转化成非严格单调递增（或者递减）序列的最小代价。
引理：在满足ans最小的情况下，一定存在一种构造序列b的方法，使得b中的数值都在a中出现过。
1 | 状态转移：F[i,j]=min{F[i-1,k]}+|A[i]-j|;(0<=k<j) |
像LCIS那题所述，优化枚举k的一维。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
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;
Sequence
比起上一题会卡空间，要优化一维。
1 |
|
P4597 序列 sequence
卡$O(N^2)$的时间复杂度啦，要用堆优化。
1 |
|
P.S.
Q：把一个序列变成非严格单调递增的，至少需要修改几个数？
A：序列A的总长度减去A的最长不下降子序列长度。
Q：把一个序列A变成严格单调递增的，至少需要修改几个数？
A：构造序列$B[i]=A[i]-i$,答案为序列总长度减去B的最长不下降子序列长度。
