cfgym100002F

201708 （ACM）动态规划----区间dp

• 其实现场就想到了区间dp，但是感觉实现很难。而且被不考虑分割的转移卡住了。
• 赛后看了题解，发现自己现场可能脑壳卡住了。不分割就直接折叠了，还犹豫啥。
• 关于实现，因为只有100^2个子串，每个子串长度100,所以dp数组直接存string就行了。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define de(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//--------
const int N=105;
string s;
string d[N][N];
int fold(int l,int r) {
    int len=r-l+1;
    rep(i,1,len/2+1) {
        if(len%i) continue;
        bool f=1;
        rep(j,l+i,r+1) {
            if(s[j]!=s[j-i]) {
                f=0;
                break;
            }
        }
        if(f) return len/i;
    }
    return -1;
}
int main() {
    freopen("folding.in", "r", stdin);
    freopen("folding.out", "w", stdout);
    while(cin>>s) { 
        int n=s.length();
        rep(len,1,n+1) {
            rep(i,0,n) {
                int j=len+i-1;
                if(j>=n) break;
                d[i][j]=s.substr(i,len);
                int t=fold(i,j);
                if(t>0) {
                    char num[10];
                    sprintf(num,"%d",t);
                    if(sz(d[i][j])>(int)strlen(num)+2+len/t) {
                        d[i][j]=string(num)+"("+d[i][i+len/t-1]+")";
                    }
                } else {
                    rep(k,i,j) {
                        if(sz(d[i][j])>sz(d[i][k])+sz(d[k+1][j])) d[i][j]=d[i][k]+d[k+1][j];
                    }
                }
            }
        }
        cout<<d[0][n-1]<<endl;
    }
    return 0;
}