关于P4302 [SCOI2003]字符串折叠因细节不同所产生的三种做法
本题的思路很简单，区间dp即可，但做题不是为了Ac，故我在此分享3种有细微差别但思路相同的做
法，以便后续遇到同类型题来选择适合自己的方法。
第一种
直接读入字符串，枚举的区间长度不包括起点
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e3+50;
char s[maxn];
int m[maxn];
int dp[maxn][maxn];
bool check(char s[],int n,int len){
for(int i=len;i<n;i++){
if(s[i]!=s[i%len]){
return false;
}
}
return true;
}
int main(){
// freopen("a.in","r",stdin);
scanf("%s",s);
int n=strlen(s);
for(int i=1;i<=9;i++){
m[i]=1;
}
for(int i=10;i<=99;i++){
m[i]=2;
}
m[100]=3;
memset(dp,inf,sizeof(dp));
for(int i=0;i<n;i++){
dp[i][i]=1;
}
for(int l=2;l<=n;l++){
for(int i=0;i+l-1<n;i++){
int j=i+l-1;
for(int k=i;k<=j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);//上界
}
for(int k=i;k<=j;k++){
int len=k-i+1;
if((l)%len!=0)
continue ;
if(check(s+i,l,len)){
dp[i][j]=min(dp[i][j],dp[i][k]+2+m[(l)/len]);
}
}
}
}
printf("%d",dp[0][n-1]);
return 0;
}
第二种
将字符串从下标1开始读入，枚举区间包含当前起点；
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e3+50;
char s[maxn];
int m[maxn];
int dp[maxn][maxn];
bool check(char s[],int n,int len){
for(int i=len;i<n;i++){
if(s[i]!=s[i%len]){
return false;
}
}
return true;
}
int main(){
// freopen("a.in","r",stdin);
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=1;i<=9;i++){
m[i]=1;
}
for(int i=10;i<=99;i++){
m[i]=2;
}
m[100]=3;
memset(dp,inf,sizeof(dp));
for(int i=0;i<=n;i++){
dp[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++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
for(int k=i;k<=j;k++){
int len=k-i+1;
if((l)%len!=0)
continue ;
if(check(s+i,l,len)){
dp[i][j]=min(dp[i][j],dp[i][k]+2+m[(l)/len]);
}
}
}
}
printf("%d",dp[1][n]);
return 0;
}
第三种
字符串从下标1读入，枚举区间不包含当前起点。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e3+50;
char s[maxn];
int m[maxn];
int dp[maxn][maxn];
bool check(char s[],int n,int len){
for(int i=len;i<n;i++){
if(s[i]!=s[i%len]){
return false;
}
}
return true;
}
int main(){
// freopen("a.in","r",stdin);
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=1;i<=9;i++){
m[i]=1;
}
for(int i=10;i<=99;i++){
m[i]=2;
}
m[100]=3;
memset(dp,inf,sizeof(dp));
for(int i=0;i<=n;i++){
dp[i][i]=1;
}
for(int l=1;l<n;l++){
for(int i=1;i+l<=n;i++){
int j=i+l;
for(int k=i;k<=j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
int le=l+1;
for(int k=i;k<=j;k++){
int len=k-i+1;
if((le)%len!=0)
continue ;
if(check(s+i,le,len)){
dp[i][j]=min(dp[i][j],dp[i][k]+2+m[(le)/len]);
}
}
}
}
printf("%d",dp[1][n]);
return 0;
}
总结
这3种做法只有细微的差别，但为什么要做，还是值得思考一下
的。
这有便于我们更好的理解区间dp;
完结撒花