文字列/部分列 DP
(test/string/subsequence_dp.test.cpp)

• View this file on GitHub
• Last update: 2023-07-21 12:14:05+09:00
• Problem: https://atcoder.jp/contests/arc081/tasks/arc081_c

Depends on

• 部分列 DP (include/emthrm/string/subsequence_dp.hpp)

Code

/*
 * @title 文字列/部分列 DP
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://atcoder.jp/contests/arc081/tasks/arc081_c
 */

#include <iostream>
#include <string>
#include <vector>

#include "emthrm/string/subsequence_dp.hpp"

int main() {
  constexpr int SIGMA = 26;
  std::string a;
  std::cin >> a;
  const int n = a.length();
  const std::vector<std::vector<int>> nxt =
      emthrm::subsequence_dp(a, 'a', SIGMA);
  std::vector<int> dp(n + 1, n + 1), next_char(n, -1);
  dp[n] = 1;
  for (int i = n - 1; i >= 0; --i) {
    for (int c = 0; c < SIGMA; ++c) {
      const int len = (nxt[i][c] == n ? 0 : dp[nxt[i][c] + 1]) + 1;
      if (len < dp[i]) {
        dp[i] = len;
        next_char[i] = c;
      }
    }
  }
  std::string ans = "";
  for (int i = 0; i < n;) {
    ans += 'a' + next_char[i];
    i = nxt[i][next_char[i]] + 1;
  }
  std::cout << ans << '\n';
  return 0;
}

#line 1 "test/string/subsequence_dp.test.cpp"
/*
 * @title 文字列/部分列 DP
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://atcoder.jp/contests/arc081/tasks/arc081_c
 */

#include <iostream>
#include <string>
#include <vector>

#line 1 "include/emthrm/string/subsequence_dp.hpp"



#include <algorithm>
#line 7 "include/emthrm/string/subsequence_dp.hpp"

namespace emthrm {

std::vector<std::vector<int>> subsequence_dp(
    const std::string& s, const char basis = 'a', const int sigma = 26) {
  const int n = s.length();
  std::vector<std::vector<int>> nx(n, std::vector<int>(sigma, n));
  nx[n - 1][s[n - 1] - basis] = n - 1;
  for (int i = n - 2; i >= 0; --i) {
    std::copy(nx[i + 1].begin(), nx[i + 1].end(), nx[i].begin());
    nx[i][s[i] - basis] = i;
  }
  return nx;
}

}  // namespace emthrm


#line 13 "test/string/subsequence_dp.test.cpp"

int main() {
  constexpr int SIGMA = 26;
  std::string a;
  std::cin >> a;
  const int n = a.length();
  const std::vector<std::vector<int>> nxt =
      emthrm::subsequence_dp(a, 'a', SIGMA);
  std::vector<int> dp(n + 1, n + 1), next_char(n, -1);
  dp[n] = 1;
  for (int i = n - 1; i >= 0; --i) {
    for (int c = 0; c < SIGMA; ++c) {
      const int len = (nxt[i][c] == n ? 0 : dp[nxt[i][c] + 1]) + 1;
      if (len < dp[i]) {
        dp[i] = len;
        next_char[i] = c;
      }
    }
  }
  std::string ans = "";
  for (int i = 0; i < n;) {
    ans += 'a' + next_char[i];
    i = nxt[i][next_char[i]] + 1;
  }
  std::cout << ans << '\n';
  return 0;
}

Back to top page