题目描述

比尔正在试图用折叠重复子序列的方式紧凑的表示由大写字母’A’到’Z’组成的字符序列。

例如，表示序列AAAAAAAAAABABABCCD的一种方式是10（A）2（BA）B2（C）D。

他通过以下方式定义了折叠的字符序列以及它们的展开变换：

1、包含带个字符的序列被认为是折叠序列，展开它得到的序列为它本身。

2、如果S和Q是两个折叠序列，并且S可以展开得到S’，Q可以展开得到Q’，则认为SQ也是一个折叠序列，并且SQ展开得到S’Q’。

3、如果S是折叠序列，则X(S)也是折叠序列，其中X为大于1的整数。如果S展开得到S’，则X(S)展开得到X个S’。

根据定义可以展开任意给出的折叠序列，现在给出原序列，请你将它折叠，并使得折叠序列包含尽可能少的字符数。

输入格式
输入包含一行由大写字母构成的字符序列，序列长度在1到100之间。

输出格式
输出包含字符数最少的折叠序列，如果答案不唯一则任意输出一个即可。

样例

输入样例：
AAAAAAAAAABABABCCD
输出样例：
9(A)3(AB)CCD

本题是在 这道题的基础上来的 本题没思路可以先做这个不统计结果
只统计个数的，再回来做此题
区间dp的思想 dp[i][j]表示a[i]~a[j]折叠后的最小长度
初始化 dp[i][j]为i~j的原始长度
然后三重循环 枚举长度l 起点i 转移点k
此题有两种转移方式 从k处折叠用 或者把k作为断点直接记录dp[i][k]+dp[k+1][j]
最后区间折叠最小值存在dp[1][n]处
然后考虑具体怎么折叠
path1[i][j]记录区间i,j的折叠处
path2[i][j]记录区间i,j的断点
两个循环分开
先写折叠的 再写断点的如果path2[i][j]存在则说明断点更优 此时认为path1[i][j]无用
之后dfs输出具体方案

C++ 代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read() {
    int x=0,y=1;
    char ch=getchar();
    while(ch>'9'||ch<'0') {if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*y;
}
const int maxn=110;
char a[maxn];//读入的字符串
int dp[maxn][maxn];
int n;//字符串长度
bool pd(int l1,int r1,int l2,int r2) {//判断是否可以折叠
    if((r2-l2+1)%(r1-l1+1)!=0)return false;
    for(int i=l2; i<=r2; i++) {
        if(a[(i-l2)%(r1-l1+1)+l1]!=a[i])return false;
    }
    return true;
}
int pre(int x) {//记录重复的个数所占的长度
    if(x==100)return 3;
    else if(x>=10)return 2;
    else return 1;
}
int path1[maxn][maxn];
int path2[maxn][maxn];
char ans[maxn];
int cnt;
void dfs(int l,int r) {
    if(l==r)  {
        putchar(a[l]);
        return;
    }
    int k1=path1[l][r];
    int k2=path2[l][r];
    if(k1==0&&k2==0) {
        for(int i=l; i<=r; i++) putchar(a[i]);
        return;
    }
    if(k2) {
        dfs(l,k2);
        dfs(k2+1,r);
        return;
    } else if(k1!=0) {
        cout<<(r-k1)/(k1-l+1)+1;
        putchar('(');
        dfs(l,k1);
        putchar(')');
    }
}

int main() {
    scanf("%s",a+1);
    n=strlen(a+1);
    for(int i=1; i<=n; i++)
        for(int j=i; j<=n; j++)
            dp[i][j]=j-i+1;
    for(int l=2; l<=n; l++) {
        for(int i=1; i+l-1<=n; i++) {
            int j=i+l-1;
            for(int k=i; k<j; k++) {
                if(pd(i,k,k+1,j)) {
                    if(pre((j-k)/(k-i+1)+1)+dp[i][k]+2<dp[i][j]) {
                        dp[i][j]=pre((j-k)/(k-i+1)+1)+dp[i][k]+2;
                        path1[i][j]=k;
                    }
                }
            }
            for(int k=i; k<j; k++) {
                if(dp[i][k]+dp[k+1][j]<dp[i][j]) {
                    dp[i][j]=dp[i][k]+dp[k+1][j];
                    path2[i][j]=k;
                }
            }
        }
    }
    dfs(1,n);
    return 0;
}