Fork me on GitHub

[思维][DP]CF1479B2

呜呜呜

题目链接

首先发现相邻位置的两个相同的元素可以被看成一个(因为求最小一定会被扔在一起),所以可以先把相邻的相同元素去重.然后发现一个元素要么在第一个队列中,要么在第二个队列中,所以我们设$f[i]$表示现在我们已经考虑了去重之后的前$i$个元素,并且第$i$个元素一定是被分在第一列中时最小的答案.那么这样之后转移就很显然了,我么枚举之前的某一段,然后把之前的那一段到现在的$i$之间的元素都加入到另一个队列中然后对答案取最大值,状态转移方程即为:

但是这样是$O(n^2)$的复杂度,所以要考虑转移的优化.我们发现有效转移点其实并不多,只有当$a[i]==a[j]$时才能产生一个使答案减小的转,所以我们对于每个$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
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int n,m,ans;
int a[N],f[N],en[N],val[N],las[N];

int main(){
scanf ( "%d", &n );
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)if(a[i]!=a[m])a[++m]=a[i];
ans=m;
f[1]=1;
las[a[1]]=1;
for(int i = 2;i <= m;i++){
f[i] = f[i-1] + (a[i] != a[i-1]);
if(las[a[i]]){
int l = las[a[i]]+1;
f[i] = min(f[i],f[l]+i-l-1);
}
las[a[i]] = i;
ans = min(ans,f[i] + m - i);
}
printf("%d\n",ans);
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:[思维][DP]CF1479B2

文章作者:兮水XiShui丶

发布时间:2021年04月27日 - 16:04

最后更新:2021年04月27日 - 17:04

原始链接:http://krrrr.top/2021/04/27/思维-DP-CF1479B2/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。