题目链接
题目大意：
折叠一个字符串，使得其成为一个尽量短的字符串 例如AAAAAA变成6（A）而且这个折叠是可以嵌套的，例如 NEEEEERYESYESYESNEEEEERYESYESYES 会变成 2(N5(E)R3(YES))。
解题报告：
用dp[i][j]表示i~j压缩的最小长度
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]
#include <map>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 105;string dp[maxn][maxn], str;
int n;int zig(int l, int r){int len = r-l+1 ;for ( int L=1; L<=len/2; ++L ){if( len%L ) continue;bool chk=true;for ( int i=l; i+L<=r; ++i )if( str[i]!=str[i+L] ){chk=false;break;}if( chk ) return L; }return 0;
}
#define Inf 0x3f3f3f3f
void work(){for ( int i=0; i<n; ++i ) dp[i][i]=str[i];for ( int i=n-2; i>=0; --i )for ( int j=i+1; j<n; ++j ){int ans=Inf, p;for ( int k=i; k<j; ++k )if( ans>dp[i][k].size()+dp[k+1][j].size() ){ans=dp[i][k].size()+dp[k+1][j].size();p=k;}dp[i][j]=dp[i][p]+dp[p+1][j];int len = zig(i,j);if( len ){char s[5];sprintf(s,"%d",(j-i+1)/len);string tmp = (string)s + "(" + dp[i][i+len-1] + ")";if( ans>tmp.size() ) dp[i][j]=tmp; }}
}int main(){while( cin>>str ){n = str.size();work();cout<<dp[0][n-1]<<endl; }return 0;
}