CF1631 E.Panit the Middle【线性DP】

题目链接：codeforces 1631E

题解

如果数字之间不影响，那么直接考虑贪心，每次选最长的区间，然后中间的改为 。但是有可能中间的数字有可能是其他区间的端点。

考虑用动态规划来解决。首先某个数字最后出现的位置一定是区间的右端点，用一个数组 pos 记录某个数字最后出现的位置。定义 dp[i] 为前 i 个 的个数。为什么是 的个数而不是 的个数呢？因为填 的位置是端点，转移的时候用端点比较好写方程。

显然，第一个数一定是左端点，定义状态转移方程： 用一个指针 cur 记录右端点的最大值，让当前最大右端点 ，即 dp[cur]，其状态转移方程为： 每次转移的时候，如果当前数字 是左端点，那么 dp[cur] 会增加 ；如果 不是左端点，那么 dp[i] 不会更新，dp[cur] 也不会更新。最后答案就是 n-dp[n]。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#incldue <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn], pos[maxn], dp[maxn];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], pos[a[i]] = i;
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    int cur = pos[a[1]];
    for (int i = 1; i <= n; i++) {
        dp[i] = min(dp[i-1] + 1, dp[i]);
        cur = max(cur, pos[a[i]]);
        dp[cur] = min(dp[i] + 1, dp[cur]);
    }
    cout << n - dp[n] << endl;
    return 0;
}