CF1919C Grouping Increases 题解
Shunpower
·
·
题解
交个傻逼另解供后人唾弃。
上了一个多月 whk 跑回来打 CF，第一发正解写挂，愤怒重构掉大分。
思路
非常自然地，我们考虑 dp。
$f_{p,0/1,i}$ 表示目前只看 $a$ 序列第 $p$ 项及其前面，$0$ 表示 $a_p\in s$，$t$ 序列最后一个数是 $a_i$ 的最小代价和；$1$ 表示 $a_p\in t$，$s$ 序列最后一个数是 $a_i$ 的最小代价和。接下来考虑转移。
- 假设 $a_p$ 接在 $s$ 当中：
- 如果 $a_{p-1}$ 也接在 $s$ 当中，那么 $f_{p,0,i}\gets \min\{f_{p-1,0,i}\}+[a_p>a_{p-1}]$。
- 如果 $a_{p-1}$ 不接在 $s$ 当中，那么 $f_{p,0,p-1}\gets \min\{f_{p-1,1,i}+[a_p>a_i]\}$。
对于 $a_p$ 接在 $t$ 当中的转移几乎是一模一样的，只有 $0/1$ 上的区别。由于第二个转移出现了按照值域分段加 $1$ 转移的情况，所以我们还要修改状态，把第三维改为表示最后一个数，而非最后一个数的下标。于是最终的结果就是这样的：
$f_{p,0/1,i}$ 表示目前只看 $a$ 序列第 $p$ 项及其前面，$0$ 表示 $a_p\in s$，$t$ 序列最后一个数是 $i$ 的最小代价和；$1$ 表示 $a_p\in t$，$s$ 序列最后一个数是 $i$ 的最小代价和。
- 假设 $a_p$ 接在 $s$ 当中：
- 如果 $a_{p-1}$ 也接在 $s$ 当中，那么 $f_{p,0,i}\gets \min\{f_{p-1,0,i}\}+[a_p>a_{p-1}]$。
- 如果 $a_{p-1}$ 不接在 $s$ 当中，那么 $f_{p,0,a_{p-1}}\gets \min\limits_{i<a_p}\{f_{p-1,1,i}+1\}+\min\limits_{a_p\leqslant i}\{f_{p-1,1,i}\}$。
- 假设 $a_p$ 接在 $t$ 当中：
- 如果 $a_{p-1}$ 也接在 $t$ 当中，那么 $f_{p,1,i}\gets \min\{f_{p-1,1,i}\}+[a_p>a_{p-1}]$。
- 如果 $a_{p-1}$ 不接在 $t$ 当中，那么 $f_{p,1,a_{p-1}}\gets \min\limits_{i<a_p}\{f_{p-1,0,i}+1\}+\min\limits_{a_p\leqslant i}\{f_{p-1,0,i}\}$。
很明显可以先滚动数组，然后做线段树优化 dp。在线段树上维护区间 $\min$，支持全局加和单点修改即可。我写得比较蠢，直接支持了区间加，其实留个全局加标记应该就行了。
两棵线段树互相转移的时候需要注意先后覆盖的问题。
## 代码
```cpp
int n;
int a[N];
int dp1[N],dp2[N];
#define mid (l+r>>1)
struct Segment_Tree{
int minn[N<<2],lzy[N<<2];
il void pushup(int p,int l,int r){
minn[p]=min(minn[p<<1],minn[p<<1|1]);
}
il void build(int p,int l,int r){
minn[p]=0;
lzy[p]=0;
if(l==r){
return;
}
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
il void pushdown(int p,int l,int r){
if(lzy[p]){
minn[p<<1]+=lzy[p];
minn[p<<1|1]+=lzy[p];
lzy[p<<1]+=lzy[p];
lzy[p<<1|1]+=lzy[p];
lzy[p]=0;
}
}
il void insert(int p,int l,int r,int d,int x){
if(d<l||d>r){
return;
}
if(l==r){
minn[p]=min(minn[p],x);
return;
}
pushdown(p,l,r);
if(d<=mid) insert(p<<1,l,mid,d,x);
else insert(p<<1|1,mid+1,r,d,x);
pushup(p,l,r);
}
il void modify(int p,int l,int r,int ml,int mr,int x){
if(ml<=l&&r<=mr){
minn[p]+=x;
lzy[p]+=x;
return;
}
pushdown(p,l,r);
if(ml<=mid) modify(p<<1,l,mid,ml,mr,x);
if(mid<mr) modify(p<<1|1,mid+1,r,ml,mr,x);
pushup(p,l,r);
}
il int query(int p,int l,int r,int ml,int mr){
if(ml>mr){
return 1e9;
}
if(ml<=l&&r<=mr){
return minn[p];
}
pushdown(p,l,r);
int ans=inf;
if(ml<=mid) ans=min(ans,query(p<<1,l,mid,ml,mr));
if(mid<mr) ans=min(ans,query(p<<1|1,mid+1,r,ml,mr));
return ans;
}
} T1,T2;
#undef mid
void solve(){
cin>>n;
fr1(i,1,n){
cin>>a[i];
}
a[0]=inf;
T1.build(1,1,n);
T2.build(1,1,n);
fr1(i,1,n){
int x=T1.query(1,1,n,1,a[i]-1),y=T1.query(1,1,n,a[i],n);
T1.modify(1,1,n,1,n,(a[i]>a[i-1]));
int minn=min(T2.query(1,1,n,1,a[i]-1)+1,T2.query(1,1,n,a[i],n));
T1.insert(1,1,n,a[i-1],minn);
T2.modify(1,1,n,1,n,(a[i]>a[i-1]));
minn=min(x+1,y);
T2.insert(1,1,n,a[i-1],minn);
}
cout<<min(T1.query(1,1,n,1,n),T2.query(1,1,n,1,n))<<'\n';
}
```
[AC Record](https://codeforces.com/contest/1919/submission/240560272)