연습 문제 9-4 uva 1630

제목:
너에게 한 줄의 숫자를 줄 테니, 그것을 접어서 길이를 가장 짧게 해라.접기 상황: 모두 알파벳 & 반복 문자열
AAAAAAAAAABABABCCD    -->   9(A)3(AB)CCD NEERCYESYESYESNEERCYESYESYES      -->       2(NEERC3(YES))
아이디어:
dp[i][j]로 i에서 j까지의 가장 짧은 상황을 나타낸다.끊임없이 아래를 찾아 i에서 j까지의 문자열을 얻은 후에 대체적인 사고방식을 접을 수 있는지 판단한다. 중간에 WR이 하나 있는데 길이를 문자형으로 바꿀 때 직접 사용하는 t+'0'을 발견했다. WR 후에 9보다 큰 것을 발견하고 이 지능은 자신을 강제로 괴롭힌다.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn = 105;
int dp[maxn][maxn];
string ans[105][105];
string s;

int judge(int l,int r)             //    
{
    int i,j;
    bool flag =true;
    for(i = 1; i <= (r-l+1)/2; i++)  
    {
        if((r-l+1) % i) continue;
        flag = true;
        for(j = l; j+i <= r; j++)
        {
            if(s[j] != s[j+i])
            {
                flag =  false;
                break;
            }
        }
        if(flag)
            return i;
    }
    return false;
}

int  dfs(int l,int r)
{
    if(dp[l][r] != -1)
        return  dp[l][r];
    if(l == r)
    {
        dp[l][r] = 1;
        ans[l][r] = s[l];
        return 1;
    }


    int tt = 0x3f3f3f3f;
    int k;
    for(int i = l; i < r; i++)                //    
    {
        int tmp = dfs(l,i) + dfs(i+1,r);         //      
        if(tt > tmp)
        {
            k = i;
            tt = tmp;
        }
    }
//    cout << l <<" " << r << endl;
    ans[l][r] = ans[l][k] + ans[k+1][r];    //      NEERC3(YES)NEERC3(YES)
    tt = dp[l][k] + dp[k+1][r];

    int flag = judge(l,r);          //        ， ：NEERC3(YES)NEERC3(YES) -> 2(NEERC3(YES))
     if(flag)
    {
        char orz[5];
        int t = (r-l+1)/flag;
        sprintf(orz,"%d",t);
        string tans = string(orz)+"("+ans[l][l+flag-1]+")";
        if(tans.size() < tt)
        {
            tt = tans.size();
            ans[l][r] = tans;
        }
    }
//    cout <<ans[l][r] <<" " << l << " " << r << endl;
    return dp[l][r] = tt;
}


int main()
{
    while(cin >> s)
    {
        int len = s.size()-1;
        memset(dp,-1,sizeof(dp));
        dfs(0,len);
        cout<<ans[0][len]<<endl;
    }
    return 0;
}