题意简要

称一个字符串

T

是好的，当且仅当存在字符串

T'

和正整数

k,(k\ge2)

，使得

T

可以通过

k

个

T'

首尾拼接得到。给定字符串

S

，求他最长的好的子序列。（不要求连续）

|S| \le 80

正文

考虑枚举

k

，拼凑两个暴力：

将 $S$ 划分成 $k$ 个部分，对于每个部分求 $LCS$ ，复杂度 $O(C_n^k\times n^{k - 1})$ （ $O(n^{2k-1})$ 是假的），能跑过 $k \le 3$ 。
将 $S$ 划分成长度为 $\displaystyle \frac{n}{k}$ 的串，则 $T'$ 一定是某个部分的子串。
证明
考虑反证法。如果不是子序列，则说明跨度 $> \displaystyle \frac{n}{k}$ 。又因为有 $k$ 段，所以跨度 $> n$ ，矛盾。
所以我们考虑求每个部分的子串，贪心匹配求答案即可。复杂度 $O(nk2^{ \frac{n}{k}})$ ，能跑过 $k \ge 5$ ，而在写代码中你只用考虑 $k = 5$ 时（可以自己想想为什么）

那

k=4

时，怎么办呢？显然，答案字符串

T = T'+T'+T'+T'=(T'+T')+(T'+T')

，在

k=2

时算过，所以不用管，然后就做完了。

code

CPP

#include <bits/stdc++.h>

using namespace std;

string s;
int n, m, f[81][81], f2[81][81][81], ans;

int LSC1(string &s, string &t){//求两个字符串的LCS，传引用更快
  memset(f, 0, sizeof f);//清空
  int l1 = s.size(), l2 = t.size();
  s = ' ' + s, t = ' ' + t;//转移下标
  for(int i = 1; i <= l1; i++){
    for(int j = 1; j <= l2; j++){
      if(s[i] == t[j])
        f[i][j] = f[i - 1][j - 1] + 1;
      f[i][j] = max({f[i][j], f[i - 1][j], f[i][j - 1]});
    }
  }//普通的nm求解
  return f[l1][l2];
}

int LSC2(string &s, string &t, string &r){//求三个字符串的LCS，传引用更快
  memset(f2, 0, sizeof f2);//清空
  int l1 = s.size(), l2 = t.size(), l3 = r.size();
  s = ' ' + s, t = ' ' + t, r = ' ' + r;//转移下标
  for(int i = 1; i <= l1; i++){
    for(int j = 1; j <= l2; j++){
      for(int k = 1; k <= l3; k++){
        if(s[i] == t[j] && t[j] == r[k])
          f2[i][j][k] = f2[i - 1][j - 1][k - 1] + 1;
        f2[i][j][k] = max({f2[i][j][k], f2[i - 1][j][k], f2[i][j - 1][k], f2[i][j][k - 1]});
      }
    }
  }
  return f2[l1][l2][l3];
}

string t, s1;//枚举s1的子串t

void dfs(int x){
  if(x == s1.size()){
    int p = 0, sz = t.size(), cnt = 0;
    if(sz > 0){
      for(char c : s){
        if(c == t[p]){
          cnt += p == sz - 1;
          p = (p + 1) % sz;
        }
      }
    }//贪心匹配
    if(cnt < 2) cnt = 0;//必须至少出现两次
    ans = max(ans, sz * cnt);
    return ;
  }
  dfs(x + 1);
  t.push_back(s1[x]);
  dfs(x + 1);
  t.pop_back();
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> s;
  n = s.size();
  for(int i = 0; i < n; i++){
    string t1 = s.substr(0, i), t2 = s.substr(i);
    ans = max(ans, 2 * LSC1(t1, t2));
  }
  for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
      string t1 = s.substr(0, i), t2 = s.substr(i, j - i), t3 = s.substr(j);
      ans = max(ans, 3 * LSC2(t1, t2, t3));
    }
  }
  int m = (n + 4) / 5;//一定得向上取整，不然会WA最后一个点，有点玄学
  for(int i = 0; i < n; i += m){
    s1 = s.substr(i, m);
    dfs(0);
  }
  cout << ans;
  return 0;
}

CF1789F题解

文章操作

正文

相关推荐

评论

CF1789F题解