题解：CF1366G Construct the String

流水行船CCD · 2025-11-12 19:45:00 · 题解

唐氏 DP 题。

原题相当于选择一个 S 的子序列和 T 相同，使得得到这个子序列所需的代价最小。那么有一个很朴素的 O(n^3) DP。

设 f_{i,j} 表示钦定 S_i 匹配 T_j，此时 S[1,i] 需要删除的最小字符数量，转移：

其中 w(l,r) 表示最少删除 S[l,r] 中的多少个字符才能使得删除后 f(S'[l,r]) 是空串。考虑 w(l,r) 的计算，有一个显然的贪心：你可以从左往右扫，遇到小写字母压栈，遇到 . 弹出栈顶，如果遇到 . 且栈为空就把答案加 1，最后答案再加上栈大小就行了。

考虑优化，你肯定考虑按 j 分层转移，每次用 j 更新 j+1，那现在就变成了一个 1d-1d 的 DP 问题：

你考虑扫描线，对于所有 l 整体维护 f'_{l-1}+w(l,i)\to f'_{l-1}+w(l,i+1) 的去权值变化量，发现这个变化量只和从 l 到 i 贪心过后栈的大小有关，因此考虑把拥有相同栈大小 l 的缩在一起。记 g_k 表示所有栈大小为 k 的 l，它们 f'_{l-1}+w(l,i+1) 的最小值。

分讨一下 i \to i+1 的变化量：

发现上述操作体现在 g 上都可以描述为全局向左/向右平移 1，全局加减，单点修改 g_0，全局最小值。

这个东西可以简单线性维护，所以总复杂度 O(n^2)。

#include<bits/stdc++.h>
#include<bits/extc++.h>
using ll = long long; using ull = unsigned long long;
#define ld std::cin
#define jyt std::cout
#define cmd std::cerr
#define REQ(i, l, r) for (int i = l; i <  r; ++i)
#define REP(i, l, r) for (int i = l; i <= r; ++i)
#define PER(i, l, r) for (int i = l; i >= r; --i)
namespace JoKing { // JoKing 12:15 10pts 
   const int N = 1e4 + 7;
   const int inf = 0x3f3f3f3f;
   int n, m, f[2][N], g[N << 1], sg[N << 1], DLT = 10002, TAG = 0;
   inline int& MAGA(int x) {return g[x + DLT];}
   inline int& MAMA(int x) {return sg[x + DLT];}
   std::string S, T;
   signed main() {
      ld >> S >> T, n = (int)S.length(), m = (int)T.length(), S = "#" + S, T = "#" + T;
      memset(f[0], 0x3f, sizeof(f[0])), f[0][0] = 0;
      REQ(TOT, 0, m) {
         int now = (TOT & 1), nxt = (now ^ 1);
         memset(f[nxt], 0x3f, sizeof(f[nxt]));
         memset(g, 0x3f, sizeof(g)), memset(sg, 0x3f, sizeof(sg)), DLT = 10002, TAG = 0;
         REP(i, TOT, n) {
            if (S[i] == T[TOT + 1]) f[nxt][i] = MAMA(0) + TAG;
            if (S[i] == '.') {
               --TAG;
               MAGA(1) = std::min(MAGA(1), MAGA(0) + 2);
               MAMA(1) = std::min(MAMA(1), MAGA(0) + 2);
               MAGA(0) = MAMA(0) = inf;
               ++DLT;
            } else {
               --DLT, ++TAG;
               MAGA(0) = inf;
               MAMA(0) = MAMA(1);
            }
            if (f[now][i] <= n) {
               MAGA(0) = std::min(MAGA(0), f[now][i] - TAG);
               MAMA(0) = std::min(MAMA(0), f[now][i] - TAG);
            } 
         }
      }
      memset(g, 0x3f, sizeof(g)), memset(sg, 0x3f, sizeof(sg)), DLT = 10002, TAG = 0;
      REP(i, m, n) {
         if (S[i] == '.') {
            --TAG;
            MAGA(1) = std::min(MAGA(1), MAGA(0) + 2);
            MAMA(1) = std::min(MAMA(1), MAGA(0) + 2);
            MAGA(0) = MAMA(0) = inf;
            ++DLT;
         } else {
            --DLT, ++TAG;
            MAGA(0) = inf;
            MAMA(0) = MAMA(1);
         }
         if (f[m & 1][i] <= n) {
            MAGA(0) = std::min(MAGA(0), f[m & 1][i] - TAG);
            MAMA(0) = std::min(MAMA(0), f[m & 1][i] - TAG);
         } 
      }
      jyt << MAMA(0) + TAG << '\n';
      return 0;
   }
}
signed main() {
#ifdef WYY
   freopen("cmd.in", "r", stdin);
   freopen("cmd.out", "w", stdout);
   double S_TIME = clock();
   cmd << "[start running]\n";
#else
   // freopen("construct.in", "r", stdin);  
   // freopen("construct.out", "w", stdout);
#endif
   std::ios::sync_with_stdio(false), ld.tie(0), jyt.tie(0);
   JoKing::main();
#ifdef WYY
   double E_TIME = clock();
   cmd << "[finished in " << E_TIME - S_TIME << "ms]\n";
//  while(true);
#endif
      return 0;
}