虽然确定了得到si+1最优状态的办法，但是同样长度的子串之间是平行关系，彼此之间还需要比较，所以我们依次遍历长度为2,3,4...n的子串，从左往右将每一个该长度的子串的最优si确定，再将长度加一，由最优的si得到最优的si+1，从而就实现了完整的状态转移，确保最后得到的sn是全局的最优情况。

参考：[

Jingyao2021-C++ sort函数用法

荼白777-The Sports Festival题解

]

Say No to Palindromes

受到前一题的影响一直在思考如何利用长度转移状态，几经尝试后发现不行，实在感觉没思路，就去看了题解，结果发现思考的很朴素，完全是在就事论事，限定字母只有"a"、"b"、"c"，三种，要想不出现回文，加入第一个是a，那么第二个可以是b也可以是c，假如第二个是b，那么第三个只能是c，第四个只能是a，第五个只能是b，第六个只能是c....发现了吗，"abc"在不断循环，总结一下：

abc
acb
bca
bac
cab
cba

只有这六个是可能出现的循环节，那我们只要依次按照这六个修改并计算所需次数就行了。但是这里还没完，每给出一个子串就重新算一遍太麻烦了，也浪费时间，有没有省事也省时一点的办法？有，利用前缀和。也就是记录前n个子串所需修改次数为 dp[n] ，那么子串 i to j 的所需修改次数就为dp[j]-dp[i] ，这个是可以证明的，想明白也不难，某种意义上来说，这才是这道题唯一体现DP思想的地方...因为这个问题的解决核心完全是就事论事，而非利用DP的某些特性去构造一些结构，所以对于一些想偷懒的人（比如我），想找到一般规律轻松解决的人，这题目就突出一个一筹莫展。（其实只是菜= =） 前缀和帮我们大大优化了时间，我们只需分别存储六种情况的修改次数的前缀和，按区间得出各种情况的值再进行比较并取最小即可，时间复杂度甚至只有O(n)，快的不可思议...

若是抛开具体事实不谈（啊对对对），这个不让出现回文的规定用长度组合转化很难解决，因为你无法保证修改某个子串的同时不影响到其他子串，更无法保证不出现新的回文子串，而若是一个个尝试...那我不敢想。这题目也体现了一点：DP不是解决问题的主要思路，他是一个优化时间的手段。如何处理回文不是由DP解决的，在有办法处理回文的情况下，通过DP思路保存子问题的解（前缀和）达到空间换时间的目的，这才是DP思想在这题中的作用。而单考虑如何修改字符串使之没有回文子串更像是一个搜索题目...虽然搜索也不好解决就是了。可以看出DP的一大特点就是题目的解决思路是很灵活的，需要各种经验与分析，这也许是因为DP扮演的角色更多是锦上添花，而非雪中送炭，做DP题是在解决各种技巧性的问题，而DP是规划这些技巧使他们快速有序的手段，两者都需要脑子，但不能只有其一。

放了这么多P话，上代码：

#include 
#include 
#include 
#include 
using namespace std;

int main(){
    string s[6]={"abc","acb","bac","bca","cab","cba"}, str;
    int a,b;
    cin>>a>>b;
    cin>>str;
    str=" "+str;    //输入区间时是从1开始计数的，所以处理数组时尽量从1开始
    int k=str.length();
    vector< vector > dp(6,vector(k));     
    for(int i=0;i<6;i++){
        for(int j=1;j>k1>>k2;
        for(int i=0;i<6;i++){
          //  cout<<"i="<

#include 
#include 
#include 
using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        int n,x,tmp;
        cin>>n>>x;
        vector< vector > dp(n+1,vector(n+1));     //规模为n*n
        vector s(n+1),ans(n+1);   //已确定规模下方切忌用push_back
        for(int i=1;i<=n;i++){
            cin>>tmp;
            s[i]=tmp;
        }
        for(int i=1;i<=n;i++){
         //   cout<<"then:";
            dp[i][0]=max(dp[i-1][0],0)+s[i];
            ans[0]=max(ans[0],dp[i][0]);
         //   cout<

#include 
#include 
#include 
using namespace std;

int main(){
    int t,n,l,max_l,max_r;
    cin>>t;
    while(t--){
        cin>>n;
        long long s=0,ss=0,dp=0;
        vector tmp(n);
        for(int i=0;i>tmp[i];
            s+=tmp[i];
            if(dp<=0) l=i;
            dp=max(dp,(long long)0)+tmp[i];
            if(dp>ss){
                max_l=l;
                max_r=i;
            }
            ss=max(ss,dp);
        }
        if(max_l==0 && max_r==n-1){		//检测最佳子串是不是全串 =s) cout<<"NO"<