专栏文章

题解：CF1366G Construct the String

流流水行船CCD
CF1366G题解参与者 4已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@min9erfh
此快照首次捕获于
2025/12/01 22:43
3 个月前
此快照最后确认于
2025/12/01 22:43
3 个月前
查看原文
唐氏 DP 题。
原题相当于选择一个 SS 的子序列和 TT 相同，使得得到这个子序列所需的代价最小。那么有一个很朴素的 O(n3)O(n^3) DP。
设 fi,jf_{i,j} 表示钦定 SiS_i 匹配 TjT_j，此时 S[1,i]S[1,i] 需要删除的最小字符数量，转移：
fi,j=min⁡k<ifk,j−1+w(k+1,i−1)f_{i,j} = \min_{k<i} f_{k,j-1} + w(k+1,i-1)
其中 w(l,r)w(l,r) 表示最少删除 S[l,r]S[l,r] 中的多少个字符才能使得删除后 f(S′[l,r])f(S'[l,r]) 是空串。考虑 w(l,r)w(l,r) 的计算，有一个显然的贪心：你可以从左往右扫，遇到小写字母压栈，遇到 . 弹出栈顶，如果遇到 . 且栈为空就把答案加 11，最后答案再加上栈大小就行了。
考虑优化，你肯定考虑按 jj 分层转移，每次用 jj 更新 j+1j+1，那现在就变成了一个 1d-1d 的 DP 问题：
fi=min⁡k<ifk′+w(k+1,i−1)f_{i} = \min_{k<i} f'_k + w(k+1,i-1)
你考虑扫描线，对于所有 ll 整体维护 fl−1′+w(l,i)→fl−1′+w(l,i+1)f'_{l-1}+w(l,i)\to f'_{l-1}+w(l,i+1) 的去权值变化量，发现这个变化量只和从 ll 到 ii 贪心过后栈的大小有关，因此考虑把拥有相同栈大小 ll 的缩在一起。记 gkg_k 表示所有栈大小为 kk 的 ll，它们 fl−1′+w(l,i+1)f'_{l-1}+w(l,i+1) 的最小值。
分讨一下 i→i+1i \to i+1 的变化量：
  1. si+1s_{i+1} 是 .：此时所有栈大小大于 00 的 ll，其 w(l,i+1)=w(l,i)−1w(l,i+1)=w(l,i)-1，且栈大小减一。而对于栈大小为 00 的 ll，其 w(l,i+1)=w(l,i)+1w(l,i+1)=w(l,i)+1，栈大小不变。
  2. si+1s_{i+1} 是小写字母：所有 ll 的 w(l,i+1)=w(l,i)+1w(l,i+1)=w(l,i)+1，且栈大小加一。
发现上述操作体现在 gg 上都可以描述为全局向左/向右平移 11，全局加减，单点修改 g0g_0，全局最小值。
这个东西可以简单线性维护，所以总复杂度 O(n2)O(n^2)。
CPP
#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;
}

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...