题解 | #01串的价值#

动态规划解法。
使用val数组来记录前i个元素的最大价值。
初始化val[0]=1。
从第二项开始遍历字符串。
对每一项，其价值最小为上一项价值+1，如221。所以先将其价值预设为最小值，val[i]=val[i-1]+1。并设置一个计数，cnt=1。
从i-1项开始，从后向前遍历字符串。当遇到与i项相同的字符时，令cnt++。当遇到不同字符时，最大价值分两种情况，一种是最大价值为前半段采用该不同字符的价值，而后半段则由之后与i项相同的连续字符串组成，即val[j] + cnt * (cnt + 1) / 2。其中cnt * (cnt + 1) / 2为连续cnt个字符的价值，是基本的等差数列求和公式。另一种情况是当前最大价值字符串中不需要该不同的字符，将其从字符串中剔除，则其不对字符串价值产生影响。val[i]不变。
当全部遍历后，计算将前面所有不同字符剔除的价值，判断其与当前价值，即保留不同字符组合而成的价值的大小关系，取最大值作为最大价值。

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    char s[n];
    for(int i = 0;i < n;i++){
        cin >> s[i];
    }
    int val[n];
    val[0] = 1;
    for(int i = 1;i < n;i++){
        val[i] = val[i - 1] + 1;
        int cnt = 1;
        for(int j = i - 1;j > -1;j--){
            if(s[j] == s[i]){
                cnt++;
            }
            else{
                if(val[i] < val[j] + cnt * (cnt + 1) / 2){
                    val[i] = val[j] + cnt * (cnt + 1) / 2;
                }
            }
        }
        if(val[i] < cnt * (cnt + 1) / 2){
            val[i] = cnt * (cnt + 1) / 2;
        }
    }
    cout << val[n - 1];
}