首页 > 代码库 > bzoj1090题解

bzoj1090题解

2024-09-28 04:58:01   215人阅读

【解题思路】

　　区间DP。设计状态f[i][j]表示压缩从第i位到第j位的字符串所需的最小长度。转移方式有三种：

•初始化：j-i+1->f[i][j]

•区间分割：f[i][k]+f[k+1][j]->f[i][j]

•子串复制（前提：子串i~j可分成长度为k的多个相同子串）：f[i][i+k-1]+digit(k)+2->f[i][j]（digit(x)表示x的十进制位数）

　　总复杂度O(n2(σ2(n)+n))。

【参考代码】

技术分享
 1 #include <bits/stdc++.h> 2 #define range(i,c,o) for(register int i=(c);i<(o);++i) 3 using namespace std; 4   5 char str[105]; 6 inline bool judge(const int&L,const int&R,const int&K) 7 { 8     range(i,0,K) for(int j=L+i;j+K<=R;j+=K) 9     {10         if(str[j]!=str[j+K]) return 0;11     }12     return 1;13 }14  15 int f[105][105];16 int main()17 {18     int N=strlen(gets(str));19     range(L,0,N) range(R,L,N) f[L][R]=R-L+1;20     range(len,2,N+1) range(L,0,N-len+1)21     {22         int R=L+len-1;23         range(i,1,int(sqrt(len))+1) if(len%i==0)24         {25             int x=i,y=len/i;26             if(judge(L,R,x)) f[L][R]=min(f[L][R],f[L][L+x-1]+int(log10(y))+3);27             if(judge(L,R,y)) f[L][R]=min(f[L][R],f[L][L+y-1]+int(log10(x))+3);28         }29         range(i,L,R) f[L][R]=min(f[L][R],f[L][i]+f[i+1][R]);30     }31     return printf("%d\n",f[0][N-1]),0;32 }
View Code

 

bzoj1090题解


联系
我们