串折叠 Folding
题面翻译
题目描述
折叠由大写字母组成的长度为 \(n\)（\(1\leqslant n\leqslant100\)）的一个字符串，使得其成为一个尽量短的字符串，例如 AAAAAA 变成 6(A)。
这个折叠是可以嵌套的，例如 NEEEEERYESYESYESNEEEEERYESYESYES 会变成 2(N5(E)R3(YES))。
多解时可以输出任意解。
Translated by @UKE自动机
输入格式
输入有多组数据。
输入若干行，第 \(i\) 行有一个仅由大写字母组成的，长度小于等于 \(100\) 的字符串。
输出格式
对于每组输入，输出折叠后的字符串。
多解时可以输出任意解。
题目描述
输入格式
输出格式
样例 #1
样例输入 #1
AAAAAAAAAABABABCCD
NEERCYESYESYESNEERCYESYESYES
样例输出 #1
9(A)3(AB)CCD
2(NEERC3(YES))
思路
我们考虑区间dp
对于每一个区间我们可以枚举他的最小重叠长度
这里要用到贪心
因为我们这里肯定是越短越好
因为前面的系数是十进制的 而括号中的一进制的
这样代码就呼之欲出了
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int dp[110][110];
string s;
bool check(int l,int r,int len){
for(int i=l;i<=r;i++)
if(s[i]!=s[(i-l)%len+l])return false;
return true;
}
void solve() {
cin>>s;s='_'+s;
int n;n=(int)s.size()-1;
memset(dp,0x3f3f,sizeof dp);
for(int i=1;i<=n;i++)dp[i][i]=1;
for(int len=2;len<=n;len++)
for(int i=1,j=len+i-1;j<=n;i++,j++)
for(int k=i;k<j;k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
int l=k-i+1;
if(len%l!=0)continue;
if(check(i,j,l))
dp[i][j]=min(dp[i][j],dp[i][k]+2+(int)log10(len/l)+1);
}
cout<<dp[1][n]<<endl;
}
signed main(){
fast
int T;T=1;
while(T--) {
solve();
}
return ~~(0^_^0);
}
有人看这里是三重循环+一重O（n）check
其实第三重 相当于是枚举因子
if(len%l!=0)continue;
这里只有sqrt（n）
所以时间复杂度是O（n3logn）
但是我们这里要输出方案
因为这里范围很小 我们就暴力维护一个二维string数组即可
空间是最多是n3的
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int dp[110][110];
string s,q[110][110];
bool check(int l,int r,int len){
for(int i=l;i<=r;i++)
if(s[i]!=s[(i-l)%len+l])return false;
return true;
}
void solve() {
s='_'+s;
int n;n=(int)s.size()-1;
memset(dp,0x3f3f,sizeof dp);
for(int i=1;i<=n;i++)q[i][i]=s[i],dp[i][i]=1;
for(int len=2;len<=n;len++)
for(int i=1,j=len+i-1;j<=n;i++,j++)
for(int k=i;k<j;k++) {
if(dp[i][j]>dp[i][k] + dp[k + 1][j]){
dp[i][j]=dp[i][k] + dp[k + 1][j];
q[i][j]=q[i][k] + q[k + 1][j];
}
int l=k-i+1;
if(len%l!=0)continue;
if(check(i,j,l))
if(dp[i][j]>dp[i][k]+2+(int)log10(len/l)+1){
dp[i][j]=dp[i][k]+2+(int)log10(len/l)+1;
q[i][j]=to_string(len/l)+'('+q[i][k]+')';
}
}
cout<<q[1][n]<<endl;
}
signed main(){
fast
int T;T=1;
while(cin>>s) {
solve();
}
return ~~(0^_^0);
}