[DP记忆化 字符串] UVa1630 Folding

DP[i][j]。i，j分别表示起始位置，终止位置，数组存该段压缩后的长度。一个串的最短压缩可以有两种情况：1.其本身是重复的，压缩其本身达到最短。2.将其分为两段，两段压缩后连接达到最短。

#include<bits/stdc++.h>
using namespace std;
const int INF= 0x3f3f3f3f;
string str;
int DP[110][110];
string fold[110][110];
int judge(int l,int r){
//judge repeat
//这里判重用的就是枚举
for(int i=1;i<=(r-l+1)/2;i++)
{
if((r-l+1)%i) continue;
bool flag=true;
for(int j=l;j+i<=r;j++)
{
if(str[j]!=str[j+i])
{
flag=false;
break;
}
}
if(flag) return i;
}
return false;
}
int fun(int l,int r){
if(DP[l][r]!=-1) return DP[l][r];
if(l==r){
DP[l][r]=1;
fold[l][r]=str[l];
return 1;
}
int k;
int re=INF;
for(int i=l;i<r;i++)
{
int tmp=fun(l,i)+fun(i+1,r);
if(tmp < re) { k=i; re=tmp; }
}
fold[l][r]=fold[l][k]+fold[k+1][r];
re=fun(l,k)+fun(k+1,r);
int len=judge(l,r);
//对重复串的压缩
if(len){
bool test=true;
for(int i=l;i<=r;i++){
if(str[i]=='('||str[i]==')') test=false; //不要把括号作为压缩对象
}
char t[10];
sprintf(t,"%d",(r-l+1)/len);
string newstr=t+string("(")+fold[l][l+len-1]+string(")");
if(test&&newstr.size()<re){
re=newstr.size();
fold[l][r]=newstr;
}
}
DP[l][r]=re;
return re;
}
int main()
{
while(cin>>str){
int R=str.size()-1;
memset(DP,-1,sizeof(DP));
fun(0,R);
cout<<fold[0][R]<<endl;
}
return 0;
}