2790 - 字符串折叠
折叠的定义如下：
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
仅一行，即最短的折叠长度。
Examples
Input
NEERCYESYESYESNEERCYESYESYES
Output
14
Solution C++
#include <iostream> #include <cstdio> #include <cstring> using namespace std; char s[101]; int f[101][101]; bool u[101][101]; bool jud(int l,int r,int cl,int cr) { if((r-l+1)%(cr-cl+1)) return false; for(int i=l;i<=r;i++) { if(s[i]!=s[(i-l)%(cr-cl+1)+cl]) return false; } return true; } int match(int x) { int t=0; while(x) { x/=10; t++; } return t; } int dp(int l,int r) { if(l==r) { return 1; } else { if(u[l][r]) { return f[l][r]; } else { u[l][r]=1; int t=r-l+1; for(int i=l;i<r;i++) { t=min(t,dp(l,i)+dp(i+1,r)); if(jud(i+1,r,l,i)) { t=min(t,dp(l,i)+2+match((r-i)/(i-l+1)+1)); } } return f[l][r]=t; } } } int main() { scanf("%s",s); printf("%d",dp(0,strlen(s)-1)); return 0; }