- #include
- using namespace std;
- intdp[55][55][55];
- string s;
- intsolve(intl,intr,int d)
- {
- if(l>r)return 0;
- if(l==r&&s[l]-'A'==d)returndp[l][r][d]=0;
- if(l==r)returndp[l][r][d]=1;
- if(dp[l][r][d]!=-1)return dp[l][r][d];
- dp[l][r][d]=1e8;
- for(inti=0;i<26;i++)
- dp[l][r][d]=min(dp[l][r][d],solve(l,r,i)+1);
- if(s[l]-'A'==d)dp[l][r][d]=min(dp[l][r][d],solve(l+1,r,d));
- if(s[r]-'A'==d)dp[l][r][d]=min(dp[l][r][d],solve(l,r-1,d));
- for(inti=l+1;i)
- {
- if(s[i]-'A'==d)
- dp[l][r][d]=min(dp[l][r][d],solve(l,i-1,d)+solve(i+1,r,d));
- }
- return dp[l][r][d];
- }
- int main()
- {
- while(cin>>s)
- {
- memset(dp,-1,sizeof(dp));
- cout<0,s.size()-1,27)<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1990543.html