luogu4302字符串折叠题解--区间DP

题目链接

https://www.luogu.org/problemnew/show/P4302

分析

很明显一道区间DP题,对于区间$[l,r]$的字符串,如果它的字串是最优折叠的,那么它的最优结果要么是所有分割出的字串最优结果之和,要么是在断点处恰好有这个区间的周期串可以进行折叠,折叠后产生的结果

状态转移

1
2
3
4
5
6
7
8
9
10
11
12
for(ri len=2;len<=n;len++){//枚举长度,套路
       for(l=1;l<=n-len+1;l++){
           r=l+len-1;
           for(ri k=l;k<r;k++){//枚举断点 
               f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);//分割出的子串结果之和 
               x=check(l,k,r);////[k+1,rr]能否由[l,k]的串循环而成  
               if(x!=-1){//如果能
                   f[l][r]=min(f[l][r],f[l][k]+2+x);//显而易见的转移
               }
           }
       }
   }

代码

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 <algorithm>
#include <cstring>
#include <cstdlib>
#include <cctype>
#define ll long long
#define ri register int
using std::min;
using std::max;
using std::swap;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=205;
int n,m,f[maxn][maxn];
char s[maxn];
inline int check(int l,int r,int rr){//[r+1,rr]能否由[l,r]的串循环而成 
    int x,st,len1=r-l+1,len2=rr-l+1;
    if(len2%len1)return -1;
    x=len2/len1;
    for(ri i=1;i<=x;i++){
        st=l+(i-1)*len1;
        for(ri j=0;j<len1;j++) if(s[l+j]!=s[st+j]) return -1;
    }
    int cnt=0;
    while(x){x/=10;cnt++;}
    return cnt;
}
int main(){
	int l,r,x;
    scanf("%s",s+1); n=strlen(s+1);
    for(ri i=0;i<=n;i++)
        for(ri j=i;j<=n;j++) f[i][j]=j-i+1;
    for(ri len=2;len<=n;len++){
        for(l=1;l<=n-len+1;l++){
            r=l+len-1;
            for(ri k=l;k<r;k++){//枚举断点 
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);//分割出的子串结果之和 
                x=check(l,k,r);//能否成为周期串 
                if(x!=-1){
                    f[l][r]=min(f[l][r],f[l][k]+2+x);
                }
            }
        }
    }
    printf("%d\n",f[1][n]);
    return 0;
}