英文题干

There are 2⋅n cards arranged in a row, with each card numbered from 1 to n having exactly 2 copies.

Each time, Red can choose a subarray of consecutive cards (at least 2 cards) to remove from the deck. The chosen subarray must satisfy that the first and last cards have the same number. The score for this operation is: the number of cards multiplied by the number on the first card. Now Red wants to know what is the maximum value of the final score?

Input:

The first line contains a positive integer — the number of card types.

The second line contains positive integers — the number on each card from left to right.

Output:

A single positive integer — representing the maximum final score.

中文题干

有 2n 张卡片排成一排，卡片编号为 1 到 n，并且都有两张编号相同的。

每次，Red可以选择一个连续的子数组（至少 2 张卡片）从牌组中移除。所选的子数组必须满足：第一张和最后一张卡片的编号相同。此操作的得分为：卡片的数量乘以第一张卡片上的数字。现在Red想知道最终得分的最大值是多少？

思路

(Inspired by 命题组)

一道区间dp。

  1. 设 的首末位置分别为(),...,()。并记是区间[]的最大贡献。

  2. 可以先假设[]的每个数的贡献都是i，如果遇到另一个区间[]满足，那么再用来替代[]这个区间的贡献。

  3. 令 dp[k] 为当前[]的最大贡献，则由定义可知 dp[]=。

    [1]. 当且时，dp[k]=max( dp(k-1)+i, dp[-1] + )

    [2]. 否则：dp[k]=dp[k-1]+i

  4. 按照区间()的长度从小到大计算即可

（P.S：一个Trick是在原数组两端补0，这样答案就是）

AC代码

时间复杂度：O()

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 3e3 + 10;

int a[maxn * 2]; // 原始序列

struct s
{
    int p1, p2; // 该数字第1次(p1)、第2次(p2)出现的索引
} sz[maxn];

ll dp[maxn * 2];
ll f[maxn];
int b[maxn]; // 存储处理顺序

inline bool cmp(int x, int y)
{
    return sz[x].p2 - sz[x].p1 < sz[y].p2 - sz[y].p1;
}

signed main()
{
    int n;
    cin >> n;

    // 初始化1~n的两个索引
    for (int i = 1; i <= 2 * n; i++)
    {
        cin >> a[i];
        if (sz[a[i]].p1 == 0)
            sz[a[i]].p1 = i;
        else
            sz[a[i]].p2 = i;
    }
    sz[0].p1 = 0, sz[0].p2 = 2 * n + 1;

    // 根据区间长度从小到大排序
    for (int i = 0; i <= n; i++)
    {
        b[i] = i;
    }
    sort(b, b + n + 1, cmp);

    for (int i = 0; i <= n; i++)
    {
        memset(dp, 0, sizeof(dp));  // 注意每一轮刷新
        int Li = sz[b[i]].p1, Ri = sz[b[i]].p2;
        for (int k = Li; k <= Ri; k++)
        {
            dp[k] = dp[k - 1] + b[i];
            if (k == sz[a[k]].p2 && sz[a[k]].p1 > Li)
            {
                dp[k] = max(dp[k], dp[sz[a[k]].p1 - 1] + f[a[k]]);
            }
        }
        f[b[i]] = dp[Ri];
    }

    cout << f[0];
    return 0;
}
// Inspired by 命题组