正題

題目鏈接:https://www.luogu.com.cn/problem/P4302

---

題目大意

一個字符串，對于一個字符串$A$?？梢詫⑦B續的$n$個$A$縮成$n(A)$。求最短的長度能夠表述出給定字符串

---

解題思路

定義$f_{i,j}$表示表示出$i～j$的字符串的最短方法。那么不考慮折疊的話有正常區間$dp$轉移即$$f_{i,j}=min\{f_{i,k}+f_{k+1,j}\}(i\le k<j)$$

然后對于一段區間$[l,r]$考慮折疊，我們枚舉長度$len$的約數$k$，判斷能否用長度為$k$的字符串折疊。有轉移$$f_{i,j}=min\{f_{i,i+k?1}+2+z_{len/k}\}(k?>[i,j])$$（$z_i$表示$i$的位數）

時間復雜度$O(n^3\sqrt{n})$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,z[110],f[110][110]; char s[110]; bool check(int l,int r,int len){if((r-l+1)%len!=0)return 0;for(int i=l+len;i<=r;i++)if(s[i-len]!=s[i])return 0;return 1; } int main() {scanf("%s",s+1);n=strlen(s+1);memset(f,0x3f,sizeof(f));for(int i=1;i<=n;i++)z[i]=z[i/10]+1,f[i][i]=1;for(int l=2;l<=n;l++){for(int i=1;i+l-1<=n;i++){int j=i+l-1;for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);for(int k=1;k<l;k++)if(check(i,j,k))f[i][j]=min(f[i][j],f[i][i+k-1]+2+z[l/k]);}}printf("%d",f[1][n]); }

總結

以上是生活随笔為你收集整理的P4302-[SCOI2003]字符串折叠【区间dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。