洛谷 4302 BZOJ 1090 SCOI2003 字符串折叠 UVA1630 Folding(输出方案版)

洛谷 4302 BZOJ 1090 SCOI2003 字符串折叠 UVA1630 Folding(输出方案版)

【题解】

  区间DP.  设f[i][j]表示i~j的最小代价。再枚举中间点k,很容易想到转移方程为f[i][j]=min(f[i][j],f[i][k]+f[k][j]),同时如果i~k可以通过重复获得i~j,那么f[i][j]=min(f[i][j],f[i][k]+len(x)+2),这里的len(x)是指重复次数在十进制下有多少位。

 #include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
#define rg register
#define N 200
using namespace std;
int n,m,f[N][N];
char s[N];
inline int read(){
int k=,f=; char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(''<=c&&c<='')k=k*+c-'',c=getchar();
return k*f;
}
inline bool check(int l,int r,int end){
int l1=r-l+,l2=end-l+;
if(l2%l1) return ;
m=l2/l1;
for(rg int i=;i<=m;i++){
int st=l+(i-)*l1;
for(rg int j=;j<l1;j++) if(s[l+j]!=s[st+j]) return ;
}
return ;
}
inline int qlen(int x){
int cnt=;
while(x){
x/=;
cnt++;
}
return cnt;
}
int main(){
scanf("%s",s+); n=strlen(s+);
for(rg int i=;i<=n;i++)
for(rg int j=i;j<=n;j++) f[i][j]=j-i+;
for(rg int l=;l<=n;l++){
for(rg int i=;i+l-<=n;i++){
int j=i+l-;
for(rg int k=i;k<=j;k++){
f[i][j]=min(f[i][j],f[i][k]+f[k+][j]);
if(check(i,k,j)){
f[i][j]=min(f[i][j],f[i][k]++qlen(m));
// printf("%d %d %d\n",i,k,j);
}
}
}
}
printf("%d\n",f[][n]);
return ;
}

  输出方案的版本。

 #include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
#define rg register
#define N 200
using namespace std;
int n,m,f[N][N],ans[N],from[N][N];
char s[N];
inline int read(){
int k=,f=; char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(''<=c&&c<='')k=k*+c-'',c=getchar();
return k*f;
}
inline bool check(int l,int r,int end){
int l1=r-l+,l2=end-l+;
if(l2%l1) return ;
m=l2/l1;
for(rg int i=;i<=m;i++){
int st=l+(i-)*l1;
for(rg int j=;j<l1;j++) if(s[l+j]!=s[st+j]) return ;
}
return ;
}
inline int qlen(int x){
int cnt=;
while(x){
x/=;
cnt++;
}
return cnt;
}
void out(int l,int r){
if(f[l][r]==r-l+){
for(rg int i=l;i<=r;i++) printf("%c",s[i]);
return;
}
int k=from[l][r];
if(check(l,k,r)){
printf("%d(",m);
out(l,k);
printf(")");
}
else{
out(l,k); out(k+,r);
}
}
int main(){
while(scanf("%s",s+)!=EOF){
n=strlen(s+);
for(rg int i=;i<=n;i++)
for(rg int j=i;j<=n;j++) f[i][j]=j-i+;
for(rg int l=;l<=n;l++){
for(rg int i=;i+l-<=n;i++){
int j=i+l-;
for(rg int k=i;k<=j;k++){
if(f[i][k]+f[k+][j]<f[i][j]){
f[i][j]=f[i][k]+f[k+][j];
from[i][j]=k;
}
if(check(i,k,j)){
int tmp=f[i][k]++qlen(m);
if(tmp<f[i][j]){
f[i][j]=tmp;
from[i][j]=k;
}
// printf("%d %d %d\n",i,k,j);
}
}
}
}
out(,n);
puts("");
}
// printf("%d\n",f[1][n]);
return ;
}
上一篇:【BZOJ】1090: [SCOI2003]字符串折叠(dp)


下一篇:ios证书