Description
折叠的定义如下:
$1.$ 一个字符串可以看成它自身的折叠。记作 $S=S$.
$2.$ $X(S)$ 是 $X(X>1)$ 个 $S$ 连接在一起的串的折叠。记作 $X(S)=SSSS…S$ ( $X$ 个 $S$ )。
如果 $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$
求给定字符串的最短折叠。
数据范围:$len<=100$
Solution
设 $f[i][j]$ 为表示区间 $[i,j]$ 折叠的最小长度。 $get(i,j,k,h)$ 表示区间 $[i,j]$ 和区间 $[k,h]$ 能否折叠。
如果能够折叠:$f[i][j]=min(f[i][j],f[i][k]+2+cal((j-i+1)/(k-i+1)))$ (其中 $cal(x)$ 返回的是 $x$ 的位数)
否则:$f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])$
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
|
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 300; string s; int f[N][N], n; bool (int x1, int y1, int x2, int y2) { if((y2 - x1 + 1) % (y1 - x1 + 1) != 0) return false; int len = y1 - x1 + 1; for(int i = x2; i <= y2; i++) { if(s[i] != s[i - len]) return false; } return true; } int cal(int k) { int ans = 0; while(k) { k /= 10; ans++; } return ans; } int main() { cin >> s; n = s.size(); for(int i = 0; i < n; i++) f[i][i] = 1; for(int i = 1; i < n; i++) { for(int l = 0; l + i < n; l++) { int r = l + i; f[l][r] = r - l + 1; for(int k = l; k < r; k++) { if(!get(l, k, k + 1, r)) f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]); else f[l][r] = min(f[l][r], f[l][k] + 2 + cal((r - l + 1) / (k - l + 1))); } } } printf("%d", f[0][n - 1]); return 0; }
|
近期评论