11. Cacey and Calphabet

11. Cacey and Calphabet

单点时限: 2.0 sec

内存限制: 256 MB

作为一个土生土长的蓝桥镇居民，Cacey 时常会去考虑一些根本没有实际应用的问题。

现有一个只由小写英文字母组成的字符串。如果字符串删去零个、一个或多个字符后可以得到 “abcdefghijklmnopqrstuvwxyz”，那么就称这个字符串为 Calphabetical（可能是希腊语）。

给出一个字符串 (s)，为了使这个字符串变成 Calphabetical 字符串，你可能需要插入一些字符。那么，你需要插入多少个字符呢？

输入格式
一行一个字符串 (s) ((1 leq |s| leq 50))。输入保证在 (s) 中只出现小写英文字母。

输出格式
输出一个整数，表示答案。

样例
input
xyzabcdefghijklmnopqrstuvw
output
3
input
aiemckgobjfndlhp
output
20

/*
思路：dp
转化为最长递增子序列做。
*/
#include<iostream>
#include<cstring>
using namespace std;
int main() {string s;cin>>s;int ans=1;int dp[s.size()];dp[0]=1;for(int i = 1 ; i < s.size(); i++) {dp[i]=1;for(int j =0; j < i; j++) {if(s[i]>s[j])dp[i]=max(dp[i],dp[j]+1);}ans=max(ans,dp[i]);}cout<<26-ans<<endl;return 0;
}