Red Playing Cards (牛客多校2 I)

进入博客阅读体验更佳:Red Playing Cards (牛客多校2 I) | 付诺の小站 (funuo0728.github.io)

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]即为最终答案。

具体操作请参考代码。

参考代码

#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;
}

相关推荐

  1. Red Playing Cards (2 I)

    2024-07-23 03:14:01       18 阅读
  2. 2024暑期训练营1 I.Mirror Maze(题解)

    2024-07-23 03:14:01       20 阅读
  3. 暑期第一场

    2024-07-23 03:14:01       14 阅读
  4. 网课:门外的树——(题解)

    2024-07-23 03:14:01       54 阅读
  5. C++知识点2

    2024-07-23 03:14:01       54 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-23 03:14:01       52 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-23 03:14:01       54 阅读
  3. 在Django里面运行非项目文件

    2024-07-23 03:14:01       45 阅读
  4. Python语言-面向对象

    2024-07-23 03:14:01       55 阅读

热门阅读

  1. Husky 入门

    2024-07-23 03:14:01       16 阅读
  2. ResNeSt

    ResNeSt

    2024-07-23 03:14:01      19 阅读
  3. 如何引入全局样式文件?

    2024-07-23 03:14:01       16 阅读
  4. 长短期记忆网络(LSTM)及其Python和MATLAB实现

    2024-07-23 03:14:01       19 阅读
  5. python的open()函数

    2024-07-23 03:14:01       12 阅读
  6. 【过题记录】 7.22

    2024-07-23 03:14:01       14 阅读
  7. linux kernel 内核缓存回收的相关配置项

    2024-07-23 03:14:01       17 阅读
  8. Asp Net Web API 请求报错

    2024-07-23 03:14:01       12 阅读
  9. 欧鹏 数据库第二次作业

    2024-07-23 03:14:01       13 阅读
  10. FTP传输的两种模式的技术原理和应用

    2024-07-23 03:14:01       15 阅读