呵呵
真不好意思,阳了竟然错过周赛了讷
qaqaq
qaqaq
废话不多说,先看题
此题应该就是一道标准的区间dp
但不过我觉得我的已经是极简了趴hhh(狂逃~
Code(C++)
#include <bits/stdc++.h>
using namespace std;
int f[1000][1000];
char a[1000];
int main(){
cin>>a;
int n=strlen(a);
memset(f,127,sizeof(f));
for(int i=0;i<n;i++) f[i][i]=1;
for(int len=2;len<=n;len++)
{
for(int l=0;l+len-1<n;l++)
{
int r=l+len-1;
if(a[l]==a[r]) f[l][r]=min(f[l+1][r],f[l][r-1]);
for(int p=l;p<r;p++)
{
f[l][r]=min(f[l][p]+f[p+1][r],f[l][r]);
}
}
}
cout<<f[0][n-1];
return 0;
}