1.元素和最小的山形三元组 II

前后缀分分解

维护pre为前缀最小值，suf为后缀最小值

​ pre[i]=min_{0}^{i} (q[i]),​suf[i]=min_{i}^{n} (q[i])

int minimumSum(vector<int>& q) {
    int n=q.size();
    vector<int> suf(n);
    suf[n-1]=q[n-1];
    for(int i=n-2;i>1;i--)
        suf[i]=min(suf[i+1],q[i]);
    int ans=INT_MAX;
    int pre=q[0];
    for(int j=1;j<n-1;j++){
        if(pre<q[j]&&q[j]>suf[j+1]){
            ans=min(ans,pre+q[j]+suf[j+1]);
        }
        pre=min(pre,q[j]);
    }
    return ans==INT_MAX?-1:ans;
}

2.合法分组的最少组数

贪心+枚举

题目等价与将k的集合划分成res个集合，集合大小为k，k+1

要分出最少的组，则最优分出最大大小的组即可，大小k受如下限制

k受min cnt[x]大小限制，最大为min cnt[x]。

k受从cnt[x]%k限制，若[cnt[x]/k] < cnt[x]%k，则k不合法，向下枚举

故既然可以对所有的集合枚举出合法的求出k，说明cnt[x]可以分成大小为k和k+1的组

此时，我们尽可能多地分出k+1组，即为本题的最佳分割方案

int minGroupsForValidAssignment(vector<int>& nums) {
    unordered_map<int,int> cnt;
    for(auto x:nums)    cnt[x]++;
    int k=min_element(
        cnt.begin(),
        cnt.end(),
        [](const auto &a,const auto &b){
            return a.second<b.second;
        }
    )->second;
    for(;;k--){
        int ans=0;
        for(auto &[_,v]:cnt){
            if(v/k<v%k){
                ans=0;break;
            }
            ans+=ceil((double)v/(k+1));
        }
        if(ans) return ans;
    }
}

3.得到 K 个半回文串的最少修改次数

划分型DP

1.求出1~200以内的数字的所有因子，ys[i]内存储i的所有因子

2.minalert[l] [r]表示以l起始，以r结尾的字符串的s子串，根据半回文串的定义创建出函数

getminalert(string s)，求出子串的最小修改次数，然后打表

3.设f数组f[i] [j]表示为将s[0]~s[i]的字符串子串划分为j段，使每个子串都变成半回文串的需要修改的最小修改次数

故​f[i][j]=min_{L=0}^{i-2} (f[L][j-1]+minalert[L+1][i])

L为枚举的切点位置，子串长度一定大于2所以切点在前i-2的位置

const int MX=201;
vector<vector<int>> ys(MX);
int init=[]{
    //i 枚举因子
    for(int i=1;i<MX;i++){
        //j 枚举包含该因子的数
        for(int j=2*i;j<MX;j+=i){
            ys[j].push_back(i);
        }
    }
    return 0;
}();

class Solution {
public:
    int getminalert(string s){
        int n=s.length(),res=n;
        //枚举该子串长度的真因子
        for(int d:ys[n]){
            int cnt=0;
            //枚举移动步长
            for(int z=0;z<d;z++){
                //枚举子串按照定义切割出的子串，计算变成回文串的最小操作次数
                for(int i=z,j=z+n-d;i<j;i+=d,j-=d){
                    cnt+=s[i]!=s[j];
                }
            }
            //得到将该子串按照可能存在的d按照定义变成半回文串的次数cnt
            res=min(res,cnt);
        }
        return res;
    }

    int minimumChanges(string s, int k) {
        int n=s.length();
        vector<vector<int>> minalert(n,vector<int> (n));
        for(int l=0;l<n-1;l++)
            for(int r=l+1;r<n;r++)
                minalert[l][r]=getminalert(s.substr(l,r-l+1));


        vector<vector<int>> f(n,vector<int>(n,n+1));
        for(int i=1;i<n;i++){
            f[i][1]=minalert[0][i];
        }
        for(int i=1;i<n;i++){
            for(int j=2;j<=min(i,k);j++){
                for(int L=0;L<i-1;L++){
                    f[i][j]=min(f[i][j],f[L][j-1]+minalert[L+1][i]);
                }
            }
        }
        return f[n-1][k];
    }
};