CF-699-div2



 2021.02.06 19:59  2023.09.01 18:14  ACM  DP 󰈭 708字

A 签到

拉垮的第一题得写半天

B 模拟暴力

发现有效的范围比较小后就很好写了

C 模拟

倒序处理，没啥意思，但是自己写起来还是写的很丑

D 构造

如果出现一对标号相同的边那么随意构造；不然的话检查m的奇偶性，如果m是奇数的话反复横跳，如果m是偶数的话还得继续考虑m/2的奇偶性，这样分类才算完全。

E DP （补题

场上用了残余的二十来分钟考虑了一阵子，妄想用一些神秘的可持久化权值线段树云云，但是好像复杂度也是n2级别的样子

正确的做法是dp

考虑这样的dp数组：dp[i]表示使得a[i..n]符合约束的最多的不需要移动的元素数量

再开设一些辅助数组：l[i]表示颜色i出现的最左边的位置，r[i]表示颜色i出现的最右边的位置，cnt[i]表示颜色i出现的次数，now[i]表示目前转移状态下颜色i出现的次数

那么从后往前转移，假设当前考虑下标i所在的位置。

如果认为a[i]不移动：

$i == l[a[i]]$，即i位置的颜色是最后一次出现，则$dp[i] = dp[r[a[i]] + 1] + cnt[a[i]]$
else，dp[i] = now[a[i]]

这是因为当i处元素还不是最左边的元素时，$r[a[i]] + 1$及以后的元素也都需要往后挪动一次，不然$l[a[i]]$没有办法和剩余的$a[i]$汇合；而当i已经是最左边的元素时，$r[a[i]] + 1$及其以后的元素不一定都要挪动一次，他们不需要为更多的$a[i]$腾出空间

如果认为a[i]移动，显然$dp[i] = dp[i +1]$

 1const itn maxn = 5e5 + 10;
 2int n;
 3int a[maxn], l[maxn], r[maxn], cnt[maxn], now[maxn], dp[manx];
 4
 5int main(){
 6    // Fastin;
 7    scnaf("%d", &n);
 8    for(int i = 0; i < n; i++) scnaf("%d", a + i);
 9    for(itn i = 0; i < n; i++) r[a[i]] = i;
10    for(int i = n - 1; i >= 0; i--){
11        l[a[i]] = i; cnt[a[i]]++;
12    }
13
14    dp[n] = 0;
15    for(int i = n - 1; i >= 0; i--){
16        now[a[i]]++;
17        if(l[a[i]] == i) dp[i] = dp[r[a[i]] + 1] + cnt[a[i]];
18        else dp[i] = now[a[i]];
19        dp[i] = max(dp[i], dp[i + 1]);
20    }
21    // prt(dp, n);
22    printf("%d\n", n - dp[0]);
23    return 0;
24}