Link。
Sol
好题!
我不是 DP 高手吗,怎么这么简单的 DP 题没场切。
考虑暴力枚举子串,显然最多有 \(n\sqrt n\) 个,这些子串一定包含答案。
对于一个串 \(t\) 和 原串 \(s\),考虑 \(s\) 是否能用 \(t\) 拼出来。
设 \(t\) 的长度为 \(len\)。
令 \(f_{i,j}\) 表示 \(i\sim j\) 最后不能被 \(t\) 拼出来的字母是否是 \(t\) 的前缀。
显然 \(f_{i,j}=f_{i,j-len}\operatorname{or}f_{i,j-2\times len}\operatorname{or}\dots\)。
注意到上面只考虑了直接拼接的情况,有可能还可以直接匹配,故 \(f_{i,j}\) 还可以被 \(f_{i,j-1}\operatorname{and} [s_j=t_{(j-i+1)\bmod len}]\)。
Code
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define desktop "C:\\Users\\MPC\\Desktop\\"
#define IOS ios :: sync_with_stdio (false),cin.tie (0),cout.tie (0)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> PII;
const int dx[] = {1,0,-1,0},dy[] = {0,-1,0,1};
template <typename T1,typename T2> bool tomax (T1 &x,T2 y) {
if (y > x) return x = y,true;
return false;
}
template <typename T1,typename T2> bool tomin (T1 &x,T2 y) {
if (y < x) return x = y,true;
return false;
}
LL power (LL a,LL b,LL p) {
LL ans = 1;
while (b) {
if (b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
int fastio = (IOS,0);
#define endl '\n'
#define puts(s) cout << s << endl
const int N = 210;
int n;
string s,s2;
string ans;
bool f[N][N];
bool check (int len) {
memset (f,0,sizeof (f));
for (int i = n;i >= 1;i--) {
f[i][i - 1] = 1;
for (int j = i - 1;j <= n;j++) {
if (f[i][j]) {
for (int l = j + len;l <= n;l += len) f[i][l] |= f[j + 1][l];
f[i][j + 1] = s[j + 1] == s2[(j - i + 1) % len + 1];
}
}
}
return f[1][n];
}
int main () {
int T;
cin >> T;
while (T--) {
cin >> s;
n = s.size ();
s = ' ' + s;
for (int len = 1;len <= n;len++) {
if (n % len == 0) {
ans = " ";
for (int i = 1;i <= n + 1;i++) ans += (char)('z' + 1);
for (int i = 1;i <= n - len + 1;i++) {
int j = i + len - 1;
s2 = " ";
for (int k = i;k <= j;k++) s2 += s[k];
if (s2 < ans && check (len)) ans = s2;
}
if (ans[1] <= 'z') {
for (int i = 1;i <= len;i++) cout << ans[i];
cout << endl;
break;
}
}
}
}
return 0;
}
标签:return,int,LL,len,long,字符串,ZYB,define
From: https://www.cnblogs.com/incra/p/18528385