模拟+贪心——cf1131E

超级恶心的题，写了好久，直接倒序模拟做，但是网上有博客好像是直接正序dp做的。。

因为左端点和右端点是永远不会变的，然后情况要考虑全

/*
从后往前插
只要记录左连续，右连续，中间连续
左端点一定是L,右端点一定是R 
*/
#include<bits/stdc++.h>
#include<string>
using namespace std;
#define maxn 100005
string s[maxn];
int n,len1,len2,ans,flag;
char L,R,c;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i];
    int len=s[n].size();
    L=s[n][0],R=s[n][len-1];
    for(int i=0;i<len;i++)
        if(s[n][i]==L)len1++;
        else break;
    for(int i=len-1;i>=0;i--)
        if(s[n][i]==R)len2++;
        else break;
    ans=1;
    int cnt=1;
    for(int i=0;i<len;i++)
        if(s[n][i]==s[n][i+1])ans=max(ans,++cnt);
        else cnt=1;
        
    if(L==R && ans==len)flag=1;//当前串同色 
    
    for(int i=n-1;i>=1;i--){
        len=s[i].size();
        //维护ans 
        int tmpl=0,tmpr=0,cntl=0,cntr=0;
        for(int j=0;j<len;j++)//求最长的和L同色的连续块 
            if(s[i][j]==L)
                cntl=max(cntl,++tmpl);
            else tmpl=0;
        
        for(int j=0;j<len;j++)//求最长的和R同色的连续块 
            if(s[i][j]==R)
                cntr=max(cntr,++tmpr);
            else tmpr=0;
        
        if(flag){//如果t串同色 
            ans=max(ans,cntl*(len1+1)+len1);
        }
        else {//如果t串不同色
            if(cntl)
                ans=max(ans,1+len1); 
            if(cntr)
                ans=max(ans,1+len2);
            if(L==R &&cntl &&cntr)
                ans=max(ans,1+len1+len2);
        }
        
        if(flag){ //维护前后缀长度 
            tmpl=len1,tmpr=len2;
            for(int j=0;j<len;j++)
                if(s[i][j]==L)len1+=(1+tmpl);
                else {flag=0;break;}
            for(int j=len-1;j>=0;j--)
                if(s[i][j]==R)len2+=(1+tmpr);
                else {flag=0;break;}
        }
        
        ans=max(ans,max(len1,len2));
    }
    cout<<ans<<endl;
}