记录编号	413016	评测结果	AAAAAAAAAA
题目名称	2409.[SCOI 2007]压缩	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2017-06-10 17:27:41	内存使用	0.34 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define LL long long
using namespace std;
int n,f[55][55],a[55][55];
string x;
int min(int a,int b)
{
    return a<b? a:b;
}
int check(int i,int j)
{
    for(int k=1;k<j-i;k++)
       if(x[i+k-1]!=x[j+k-1])
          return 0;
    return 1;
}
int main()
{
    freopen("compress.in","r",stdin);
    freopen("compress.out","w",stdout);
    cin>>x;
    n=x.size();
    memset(f,10,sizeof(f));
    for(int i=1;i<=n;i++)
       f[i][i]=2;
    f[1][1]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
           f[i][j]=min(f[i][j],f[i][j-1]+1);
           if(x[i-1]==x[j-1]&&check(i,j))
               f[i][j*2-i-1]=min(f[i][j*2-i-1],f[i][j-1]+1);
        }       
    }
    
    for(int i=1;i<=n;i++)
       for(int j=i+1;j<=n;j++)
          for(int k=i;k<j;k++)
             f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
  /*  for(int i=1;i<=n;i++)
       cout<<i<<" ";
    cout<<endl<<endl;
    for(int i=1;i<=n;i++){
       for(int j=1;j<=n;j++)
         cout<<f[i][j]<<" ";
         cout<<endl;
    }*/
    cout<<f[1][n];
    //while(1);   
}