BZOJ4553 序列
题目链接：序列 - 黑暗爆炸 4553
显然，这是一道dp题。我们首先需要考虑什么样的情况才能使得任意一种变化中，一个子序列能恒为不降序列。设我们有一个子序列 \(S\)。考虑其中相邻的两个点 \(i,j\)。由于我们必须满足所有变化中 \(v_j>=v_i\)，同时，题意告诉我们，每种变化最多只有一个值发生变化，意思是，有一个位置的值发生变化了别的就不会发生变化了。所以我们设 \(max_x\) 表示 \(x\) 这个位置在所有变化中的最大值，\(min_x\) 表示在 \(x\) 这个位置所有变化中的最小值，\(Val_i\) 表示 \(x\) 这个位置在这个位置不变化的情况中的值。那么对于我们上述提到的 \(i,j\) 两个位置。当且仅当满足 \(Val_j\ge max_i\) 且 \(min_j\ge Val_i\) 时，他们两个在任意一种变化情况中 \(j\) 的值都是大于等于 \(i\) 的值得。我们可以写出一个暴力dp。转移式如下：
\[dp_i=\max_{j=1}^{i-1}(dp_j)+1(Val_i\ge max_j,min_i\ge Val_i) \]代码实现如下：
for(int i=1;i<=n;++i)
{
dp[i]=1;
for(int j=1;j<i;++j)
{
if(v[i]>=mx[j]&&mi[i]>=v[j])
dp[i]=max(dp[i],dp[j]+1);
}
}
但是这个暴力dp的时间复杂度是 \(O(n^2)\) 的，肯定通过不了这道题。那么我们得考虑优化，我们发现传统的dp优化都解决不了这个问题。但是，注意到这个dp是一维的，而且他的转移一次的代价是 \(O(n)\) 的。那么显然这是一种 1D/1D 的动态规划。对于 1D/1D 的动态优化在条件良好的情况下我们可以用 cdq分治将这类问题的时间复杂度由 \(O(n^2)\) 降至 \(O(n\times\log(n)\times\log(n))\) 。oiwiki中有提到，可以去看看 CDQ 分治。
这个dp 除了上面提到的两个条件，其实还有一个条件为 \(i<j\)。根据上述列出的条件 \(Val_j\ge max_i,min_j\ge Val_i,i<j\)，那么这个问题就变成了一个三维偏序的问题，我们用cdq分治来维护，1D 排序，2D cdq，3D树状数组，可以很好的解决这个问题。
注意，cdq分治优化dp，调用cdq函数递归的顺序以及排序调用有所变化，具体变化的原因可以在上面那个oiwiki的链接中查看，里面有详细的阐述。
代码如下：
#include<bits/stdc++.h>
#define lowbit(i) (i&(-i))
using namespace std;
const int MAXN = 1e5+5;
const int MX = 1e5;
int n,m,dp[MAXN],t[MAXN];
void upd(int pos,int x){for(int i=pos;i<=MX;i+=lowbit(i))t[i]=max(t[i],x);}
void clear(int pos){for(int i=pos;i<=MX;i+=lowbit(i))t[i]=0;}
int query(int pos){int ans=0;for(int i=pos;i;i-=lowbit(i))ans=max(ans,t[i]);return ans;}
struct node
{
int v,min_v,id,max_v;
}a[MAXN];
bool cmp1(node a,node b)
{
return a.id<b.id;
}
bool cmp2(node a,node b)
{
return a.v<b.v;
}
bool cmp3(node a,node b)
{
return a.min_v<b.min_v;
}
void cdq_solve(int l,int r)
{
if(l==r)
{
dp[a[r].id]++;
return ;
}
int mid=l+r>>1;
cdq_solve(l,mid);
sort(a+l,a+mid+1,cmp2);sort(a+mid+1,a+r+1,cmp3);
int cur=l;
for(int i=mid+1;i<=r;++i)
{
while(a[cur].v<=a[i].min_v&&cur<=mid)
upd(a[cur].max_v,dp[a[cur].id]),++cur;
dp[a[i].id]=max(dp[a[i].id],query(a[i].v));
}
for(int i=l;i<cur;++i)
clear(a[i].v);
sort(a+mid+1,a+r+1,cmp1);
cdq_solve(mid+1,r);
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i].v),a[i].min_v=a[i].v,a[i].id=i,a[i].max_v=a[i].v;
for(int i=1;i<=m;++i)
{
int pos,x;
scanf("%d %d",&pos,&x);
a[pos].min_v=min(a[pos].min_v,x);
a[pos].max_v=max(a[pos].max_v,x);
}
sort(a+1,a+1+n,cmp1);
cdq_solve(1,n);
int ans=0;
for(int i=1;i<=n;++i)
ans=max(ans,dp[i]);
printf("%d\n",ans);
return 0;
}
总结：算是cdq优化1D/1D问题的模板了，适合我这种菜鸡练手。