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’, BB’,则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; }