dd爱科学2.0

大科学家 $dd$ 最近在研究转基因白菜，白菜的基因序列由一串大写英文字母构成， $dd$ 经过严谨的推理证明发现，只有当白菜的基因序列呈按位非递减形式时，这株白菜的高附加值将达到最高，于是优秀的 $dd$ 开始着手修改白菜的基因序列， $dd$ 每次可以选择基因序列的一位进行修改，每次当她把一个字母 $x$ 修改成 $y$ 时，会产生 $|x-y|$ (即 $x$ 与 $y$ 的 $ASCII$ 码差值的绝对值)的改动偏移量， $dd$ 希望，修改白菜的基因序列使其高附加值达到最高，并且基因序列的改动偏移量总和最小，她想知道最小的改动偏移量总和是多少。

#include<iostream> #include<cmath> using namespace std; string s; int n,a[27]; int main(){ cin>>n>>s; for(int i=0;i<n;i++){ int x=1e9; for(int j=1;j<=26;j++){ x=min(x,a[j]); a[j]=x+abs(j-(s[i]-'A'+1)); } } int ans=2e9; for(int i=1;i<=26;i++) ans=min(ans,a[i]); cout<<ans<<endl; return 0; }

详情