CF1866J

· · 题解

题目大意：

有两个栈，初始一个栈为空，并且有以下两次操作，问吧所有数删掉最小代价是多少。

  1. 将某一个栈顶的第一个数移到另一个栈栈顶。
  2. 将某一个栈顶的一个极大相同的数全删掉。

    解题思路：

    我们分析一下样例的解释，会发现一下几点性质：

  3. a 数组中每一个极大连通块都是在同一个栈里且一起被删除的。
  4. 每一个数顶多从第一个栈移到第二个栈再移到第一个栈，且那时下一步一定是删掉。
  5. 每次删完之后和之前的拼在一起，一定是一段区间。

所以，我们在把 a 的每一个极大连通块缩成一个二元组存数值和个数后。
注：以下说的 a 是缩完连通块时候的数组，b 表示 a 出现的个数。
设 dp_{l, r} 表示 l \sim r 的区间全部删除的最小花费。
我们考虑一下 a_{l} 是和谁在一起最后删掉的，但他们可能是 一些 数字，就比如下图： 他们可能是很多段，假设选出的数的下标为 id_{1}, id_{2}, \dots id_{k}，那么考虑会有两种方案去将他们合到一起：

  1. 首先将 id_{1}, id_{2}, \dots id_{k-1} 移到右边，然后由于 id_{k} 的集合过大，又将 id_{1}, id_{2}, \dots id_{k-1} 移回左侧，直接删掉，代价是 2 \times \sum_{i=1}^{k-1}b_{id_{i}} + X + \sum_{i=1}^{k-1}dp_{id_{i} + 1, id_{i+1}-1}。
  2. 那么还有一种可能，就是 b_{id_{k}} 没有那么大，所以是将 id_{k} 移到右边后，直接删掉，代价为 \sum_{i=1}^{k}b_{id_{i}} + X + \sum_{i=1}^{k-1}dp_{id_{i} + 1, id_{i+1}-1}。

通过上面的式子，合起来后发现会有 min 的符号，那么考虑分别考虑，设 f_{l, r} 表示 l \sim r 的第一种情况答案，g_{l, r} 表示 l \sim r 的第二种情况答案。
因为我们 dp 调用时，是保证 a_{l} = a_{id_{k}} 的，所以我们的 f,g 都可以强制 l 和 r 都被选。
考虑转移 f，那么枚举 id_{k-1}，因为 id_{k} = r，就有：

f_{l,r} = \min_{a_{pos} = a_{l}} f_{l, pos} + dp_{pos+1,r}+2 \times b_{r}

当然，在给 dp 更新答案时记得减去 2 \times b_{r}。
g 数组同理：

g_{l,r} = \min_{a_{pos} = a_{l}} g_{l, pos} + dp_{pos+1,r}+b_{r}

dp 数组就是枚举 id_{k} 的位置：

dp_{l, r} = \min_{a_{l} = a_{pos}} \min(f_{l, pos} - 2 \times b_{pos}, g_{l, pos}) + dp_{pos + 1, r} + X

显然易见，O(n^3)。
创作不易，点个赞吧 QWQ！

CODE：


#include <bits/stdc++.h>
using namespace std;
int m, X, Y, n, a[405];
long long b[405], dp[405][405], g[405][405], f[405][405];
int main(){
    scanf("%d%d%d", &m, &X, &Y);
    for(int i = 1; i <= m; i++){
        int x;
        scanf("%d", &x);
        if(a[n] == x) b[n]++;
        else a[++n] = x, b[n] = 1;
    }
    for(int i = 1; i <= n; i++) b[i] *= Y; //为了方便
    memset(dp, 0x3f, sizeof(dp));
    memset(f, 0x3f, sizeof(f));
    memset(g, 0x3f, sizeof(g));

    for(int i = 1; i <= n; i++){
        dp[i][i] = X, f[i][i] = 2 * b[i], g[i][i] = b[i];//边界
    }
    for(int i = 1; i <= n + 1; i++){
        dp[i][i - 1] = f[i][i - 1] = g[i][i - 1] = 0; //边界
    }

    for(int len = 2; len <= n; len++){
        for(int l = 1; l + len - 1 <= n; l++){
            int r = l + len - 1;
            if(a[r] == a[l]){ //条件
                for(int pos = l; pos < r; pos++){ //f
                    if(a[pos] == a[l]){
                        f[l][r] = min(f[l][r], f[l][pos] + dp[pos + 1][r - 1] + b[r] * 2);
                    }
                }
                for(int pos = l; pos < r; pos++){ //g
                    if(a[pos] == a[l]){
                        g[l][r] = min(g[l][r], g[l][pos] + dp[pos + 1][r - 1] + b[r]);
                    }
                }
            }
            for(int pos = l; pos <= r; pos++){
                if(a[pos] == a[l]){
                    dp[l][r] = min(dp[l][r], min(f[l][pos] - 2 * b[pos], g[l][pos]) + dp[pos + 1][r] + X);
                }
            }
        }
    }
    printf("%lld", dp[1][n]);
    return 0;
}