Red Playing Cards

题目大意

有$2n$的数组成一个序列，其中$1$到$n$每个数都会出现两次。你可以执行以下操作：

选择两个端点相同的区间，删去这个区间，同时获得$区间长度 \times 区间端点数$的分数。

求所能获得的最大分数为多少。

解题思路

考虑线性$DP$，$f[i]$表示只考虑前$i$个数所能获得的最大分数，思考状态转移：

  • 当$[1, i - 1]$中没有数与$a[i]$相同，$f[i] = f[i - 1]$；
  • 当$[1, i - 1]$中有数与$a[i]$相同，假设其下标为$l$，那么状态转移为$f[i] = f[l - 1] + g[l][i] + (i - l + 1)\cdot a[i]$，其中$g[i][j]$表示这段区间最多能获得的分数比单纯用两端点删掉$[l, r]$这一区间所获得的分数要大多少；

注意到引入了新的状态，说明这种想法不太可行，但同时$g[i][j]$也启发我们，只有在区间$[i + 1, j - 1]$中有两端点大于$a[i]$的可操作区间，$g[i][j]$才有值，而如果存在多个这样的可操作区间，就考虑类似$01$背包的想法，对可操作区间进行操作与不操作的状态转移即可。于是，就想到了重新定义状态：

$f[i]$表示区间端点为$i$的区间$[l, r]$可获得的最大分数，状态转移则对区间$[l + 1, r - 1]$中的可操作区间对于操作与不操作取个$max$即可，由于可操作区间的端点一定大于$i$，所以$i$应该从大到小进行遍历。

小$trick$：如果将第$0$位和第$2n + 1$位上的数置为$0$，并考虑$f[0]$，那么$f[0]$即为最终答案。

具体操作请参考代码。

参考代码

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
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#define maxn 6010
#define int long long
using namespace std;
const double eps = 1e-8;
int a[maxn], l[maxn], r[maxn];

void solve() {
    int n;  cin >> n;
    n <<= 1;
    for (int i = 1; i <= n; ++i)  cin >> a[i];
    l[0] = 0;  r[0] = n + 1;
    for (int i = 1; i <= n; ++i) {
        if(!l[a[i]])  l[a[i]] = i;
        else  r[a[i]] = i;
    }
    vector<int> f(n / 2 + 1, 0);
    for (int i = n / 2; i >= 0; --i) {
        vector<int>g(n + 2, 0);
        for (int j = l[i] + 1; j < r[i]; ++j) {
            g[j] = max(g[j], g[j - 1] + i);
            if(j == l[a[j]] && r[a[j]] < r[i])  g[r[a[j]]] = max(g[r[a[j]]], g[j - 1] + f[a[j]]);
        }
        f[i] = 2 * i + g[r[i] - 1];
        // cout << i << ": " << f[i] << '\n';
    }
    cout << f[0] << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}