uva 1630——Folding

系统管理员 2022-08-18 11:32 119阅读 0赞

题意：给出一个由大写字母组成的长度为n的串，然后尽量折叠成一个尽量短的串，折叠可以嵌套。

思路：区间dp，dp（i，j）表示区间（i，j）的最短的串的长度，as（i，j）表示i到j的答案，有两个状态要处理：1.该串本身是重复串，缩段到最短。2.该串不是重复，然后枚举他的分割点把两段最短找出来，然后合并。

code：

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=1000000;
    const int M=105;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define ft(i,s,n) for (int i=s;i<=n;i++)
    #define frt(i,s,t) for (int i=s;i>=t;i--)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int dp[M][M];
    string s;
    string as[M][M];
    int check(int l,int r){
        ft(i,1,(r-l+1)/2){
            if ((r-l+1)%i) continue;
            bool f=1;
            ft(j,l,r-i)
                if (s[j]!=s[j+i])
                {
                    f=0;
                    break;
                }
            if (f) return i;
        }
        return 0;
    }
    int sol(int l,int r){
        int& ans=dp[l][r];
        if (ans!=-1) return ans;
        if (l==r){
            as[l][r]=s[l];
            return ans=1;
        }
        int ret=INF,k;
        ft(i,l,r-1){
            int tp=sol(l,i)+sol(i+1,r);
            if (tp<ret) k=i,ret=tp;
        }
        as[l][r]=as[l][k]+as[k+1][r];
        ret=sol(l,k)+sol(k+1,r);
        int t=check(l,r);
        if (t){
            bool f=1;
            ft(i,l,r)
            if (s[i]=='('||s[i]==')') f=0;
            char ts[10];
            sprintf(ts,"%d",(r-l+1)/t);
            string tt=ts;
            tt+="("+as[l][l+t-1]+")";
            if (f&&tt.size()<ret){
                ret=tt.size();
                as[l][r]=tt;
            }
        }
        return ans=ret;
    }
    int main()
    {
        while(cin>>s){
            cls(dp,-1);
            int len=s.size()-1;
            sol(0,len);
            cout<<as[0][len]<<endl;
        }
    }