本文主要是介绍18942 偏爱字母，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
经验谈：初期学习时肯定会这种情况，看到算法题目，感觉不难，但又做不出来的情况。解决算法题目本质上是看出题目要考察的知识点，再编码实现。当一个问题出现时，可以先借鉴暴力枚举的思想，先思考下答案到底是什么？将问题转换成我们熟悉的形式。
例如本题，求某个满足条件的子串，也就是求满足条件的区间。那么一定可以用暴力枚举的方式得到所有区间，再计算得到答案。这样就得到一个复杂度O(n^3)的算法（这样考试不会得0分了）。然后再考虑如何能优化这个问题，实际上此题目是最大子段和问题。
解题思路：将F看成-1，E看成1，这样问题就转换成求区间最大和问题，即最大子段和问题。下面代码使用了一种简单的dp思想来解决问题，即第i个字符或者和前面第i-1字符组成的最大子串连在一起，或者自己单独做一个子串。
#include <bits/stdc++.h>//ASI
using namespace std;
int main()
{int i,j,n,sum=0,ans=0;string s;cin>>n>>s;for(i=0;i<s.size();i++){if(s[i]=='E')sum++;else if(s[i]=='F')sum--;if(sum<0) /**< 如果到这里总和小于0，对于后面的第i+1来说，独立要比和第i个连接更好 */sum=0;ans=max(ans,sum);}cout<<ans;return 0;
}
这篇关于18942 偏爱字母的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
