Leetcode第 368 场周赛

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

预处理前缀和后缀最小值,记为pre[i]和sa[i]
对于当前编号i，如果前面的最小值和后面的最大值都小于nums[i],则记录ans[i] = nums[i]+pre[i-1]+sa[i+1]
结果输出最小的ans[i]即可。

合法分组的最少组数

统计每一个数字出现的次数。将每一个数字分为大小为$d$或$d+1$的组，令$d$尽可能大。
$d$不满足单调性，不好二分。思路时直接暴力。
计最小出现次数为$mn$,出现过的数字个数为$cnt$，显然有$mn\ast cnt\le nums.length$
而显然有$d+1\le mn$,因此直接枚举d
对于某个数字i，其出现次数为$to{t}_i$,若$d$成立则需要满足存在x令$xd\le to{t}_i\le x(d+1)$
令$x=to{t}_i/d$，即以$d$为标准将$to{t}_i$分为x组，此时还剩$to{t}_i\%d$个元素，每一组中最多可以容纳$d+1$个元素，最多可以容纳x个元素，使x组的个数都变为%d+1%。因此只要满足$to{t}_i\%d\le x$即$to{t}_i\%d\le to{t}_i/d$，则对数字$i$而言$d$是合法的分组。
已知d，数字i的分组个数为$\frac{to{t}_i+d}{mn+1}$。$x$需要取最小值满足$xd\le to{t}_i\le x(d+1)$,有 $\lceil to{t}_i/(d+1)\rceil \le x$，因此取$x=\lceil \frac{to{t}_i}{d+1}\rceil$
枚举$d$,计算分组个数，求分组最小值即可,复杂度为$O(mn\ast cnt)$

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

数据只有200，想法是纯暴力
令$MinTimes[i][j]$为子串$st{r}_{ij}$变成半回文串最少的次数，暴力计算，复杂度为$O(n^4)$
令dp[i][j]为以$st{r}_i$为结尾时分为$j$段最少的操作次数
$$dp[i][j]=\min dp[z][j-1]+MinTimes[z+1][i]$$
总复杂度$O(n^4)$
计算MinTimes时可以将一个n优化成$\sqrt{n}$甚至预处理成$\lg n$，但是$O(n^4)$也能过就是了,大概是数据比较弱吧

class Solution {
public:int MinTimes[210][210];int dp[210][210];int calTimes(string &s,int l,int r){int ret = (1<<30);int len = r-l+1;while(--len){if((r-l+1)%len)continue;int ans = 0;for(int i=0;i<len;++i){string t1;for(int j=l+i;j<=r;j+=len)t1 += s[j];for(int c=0;c<t1.size()/2;++c)if(t1[c]!=t1[t1.size()-1-c])ans++;}ret = min(ret,ans);}return ret;}int minimumChanges(string s, int k) {memset(dp,0x3f,sizeof(dp));dp[0][0] = 0;int l = s.size();     for(int i=0;i<l;++i){for(int j=i+1;j<l;++j){MinTimes[i][j] = calTimes(s,i,j);}MinTimes[i][i] = (1<<30);}for(int i=0;i<l;++i){for(int j=0;j<=i;++j){for(int z=1;z<=k;++z){dp[i+1][z] = min(dp[i+1][z],dp[j][z-1]+MinTimes[j][i]);}}}return dp[l][k];}
};