现在的位置: 首页 > 综合 > 正文

【bzoj 1090】: [SCOI2003]字符串折叠

2017年04月26日 ⁄ 综合 ⁄ 共 2052字 ⁄ 字号 评论关闭

1090: [SCOI2003]字符串折叠

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 587  Solved: 386
[Submit][Status]

Description

折叠的定义如下: 1. 一个字符串可以看成它自身的折叠。记作S  S 2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S)  SSSS…S(X个S)。 3. 如果A  A’, BB’,则AB  A’B’ 例如,因为3(A) = AAA, 2(B) = BB,所以3(A)C2(B)  AAACBB,而2(3(A)C)2(B)AAACAAACBB
给一个字符串,求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为:9(A)3(AB)CCD。

Input

仅一行,即字符串S,长度保证不超过100。

Output

仅一行,即最短的折叠长度。

Sample Input

NEERCYESYESYESNEERCYESYESYES

Sample Output

14

HINT

一个最短的折叠为:2(NEERC3(YES))

一直不会这种题,原来就是直接暴力地记忆化

这题还可以输出方案,具体差不多,可以参考http://hzwer.com/3621.html

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive
************************************************/
/////////////////////////////////////////////////
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
/////////////////////////////////////////////////
char s[101];
int len;
int dp[101][101];
/////////////////////////////////////////////////
bool check(int l,int r,int cl,int cr)
{
    //r-l+1 cr-cl+1
    if((cr-cl+1)%(r-l+1)!=0) return 0;
    rep(i,cl,cr)
        if(s[i]!=s[(i-l)%(r-l+1)+l]) return 0;
    return 1;
}
inline int get(int x)
{int res=0;while(x)x/=10,res++;return res;}
int DP(int l,int r)
{
    if(dp[l][r]!=-1) return dp[l][r];
    if(l==r) return dp[l][r]=1;
    int ans=r-l+1;
    rep(i,l,r-1)
    {
        ans=min(ans,DP(l,i)+DP(i+1,r));
        if(check(l,i,i+1,r))
            ans=min(ans,DP(l,i)+get((r-i)/(i-l+1)+1)+2);
    }
    //printf("dp[%d][%d]=%d\n",l,r,ans);
    return dp[l][r]=ans;
}
/////////////////////////////////////////////////
void input()
{
    scanf("%s",s+1);
    len=strlen(s+1);
}
void solve()
{
    ///////////////////init///////////////////
    MS(dp,-1);
    ////////////////calculate////////////////
    
    /////////////////output/////////////////
    printf("%d\n",DP(1,len));
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    input();
    solve();
    #ifdef _TEST
    for(;;);
    #endif
    return 0;
}

抱歉!评论已关闭.