一眼区间 \(dp\), 但蒟蒻的我还是调了好久 \(qwq\)
[状态设置]
设 \(f[i][j]\) 为子串 \([i,j]\) 的最短折叠
最后答案为 \(f[1][n]\) 废话
[初始化]
\(1\) 首先对于任意的 \(i\) 必然存在 \(f[i][i]=1\)
然后其他的都初始化为 \(INF\) 即可
\(2\) 因为最后的字符串可能会出现数字, 所以不妨考虑用一个数组 \(g[x]\) 预处理 \(x\) 的位数 \(qwq\)
[\(dp\) 核心]
对于任意的 \(f[i][j]\) \((i <j)\) 可以有两种得到方式.
分成两段, 两段的最短折叠连在一起构成, 即左区间 \(+\) 右区间
自身构成: 找子串 \([i,j]\) 中的一个循环子串, 形如 循环节 左括号 子串 右括号. 长度即为即循环节位数 \(+2+\) 子串长度.
第一种方式, 套区间 \(dp\) 的模板, 先枚举出 \(len\) 和 \(i\), 得到 \(j=i+len-1\), 再跑一遍 \(k\) 枚举割点, 于是得到:
\(f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])\) \((i \leq k < j)\)
第二种方式, 如果子串 \([i,k]\) 是子串 \([i,j]\) 中的一个循环子串, 则:
\(f[i][j]=min(f[i][j],g[len/l]+2+f[i][k])\) \((l=k-i+1)\)
[代码]
- #include<bits/stdc++.h>
- using namespace std;
- const int max_n=100+5;
- int n,g[max_n],f[max_n][max_n];
- string st;
- bool check(int ll,int rr,int len){// 判断是否是循环节
- for(int i=ll;i<=ll+len-1;i++){
- char ch=st[i];
- for(int j=i;j<=rr;j+=len){
- if(st[j]!=ch)return false;
- }
- }
- return true;
- }
- int main(){
- iOS::sync_with_stdio(false);
- cin>>st;
- n=st.size();st=" "+st;// 把字符串变成 1~n
- for(int i=1;i<=9;i++)g[i]=1;
- for(int i=10;i<=99;i++)g[i]=2;
- g[100]=3;//g[x] 表示 x 的位数
- memset(f,0x3f,sizeof(f));
- for(int i=1;i<=n;i++)f[i][i]=1;// 初始化 f 数组
- for(int len=1;len<=n;len++){
- for(int i=1;i+len-1<=n;i++){
- int j=i+len-1;// 区间 DP 模板, 得到 i 和 j
- for(int k=i;k<j;k++){// 枚举哪里切
- f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);// 第一种情况, 左区间 + 右区间
- int l=k-i+1;// 第二种情况, 先得到循环节的长度
- if(len%l)continue;// 长度不符
- if(check(i,j,l))f[i][j]=min(f[i][j],g[len/l]+2+f[i][k]);// 是循环节, 那么套公式
- }
- }
- }
- cout<<f[1][n]<<"\n";
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3345021.html