asp网站开发视频,白酒招商网站大全,网站建设的财务计划,手机微信一体网站建设元素和最小的山形三元组 II
预处理前缀和后缀最小值,记为pre[i]和sa[i] 对于当前编号i#xff0c;如果前面的最小值和后面的最大值都小于nums[i],则记录ans[i] nums[i]pre[i-1]sa[i1] 结果输出最小的ans[i]即可。
合法分组的最少组数
统计每一个数字出现的次数。将每一个数…元素和最小的山形三元组 II
预处理前缀和后缀最小值,记为pre[i]和sa[i] 对于当前编号i如果前面的最小值和后面的最大值都小于nums[i],则记录ans[i] nums[i]pre[i-1]sa[i1] 结果输出最小的ans[i]即可。
合法分组的最少组数
统计每一个数字出现的次数。将每一个数字分为大小为 d d d或 d 1 d1 d1的组令 d d d尽可能大。 d d d不满足单调性不好二分。思路时直接暴力。 计最小出现次数为 m n mn mn,出现过的数字个数为 c n t cnt cnt显然有 m n ∗ c n t ≤ n u m s . l e n g t h mn*cnt \le nums.length mn∗cnt≤nums.length 而显然有 d 1 ≤ m n d1 \le mn d1≤mn,因此直接枚举d 对于某个数字i其出现次数为 t o t i tot_i toti,若 d d d成立则需要满足存在x令 x d ≤ t o t i ≤ x ( d 1 ) xd \le tot_i \le x(d1) xd≤toti≤x(d1) 令 x t o t i / d x tot_i/d xtoti/d即以 d d d为标准将 t o t i tot_i toti分为x组此时还剩 t o t i % d tot_i\%d toti%d个元素每一组中最多可以容纳 d 1 d1 d1个元素最多可以容纳x个元素使x组的个数都变为%d1%。因此只要满足 t o t i % d ≤ x tot_i\%d \le x toti%d≤x即 t o t i % d ≤ t o t i / d tot_i\%d \le tot_i/d toti%d≤toti/d则对数字 i i i而言 d d d是合法的分组。 已知d数字i的分组个数为 t o t i d m n 1 \frac{tot_id}{mn1} mn1totid。 x x x需要取最小值满足 x d ≤ t o t i ≤ x ( d 1 ) xd \le tot_i \le x(d1) xd≤toti≤x(d1),有 ⌈ t o t i / ( d 1 ) ⌉ ≤ x \lceil tot_i/(d1)\rceil \le x ⌈toti/(d1)⌉≤x因此取 x ⌈ t o t i d 1 ⌉ x \lceil \frac{tot_i}{d1}\rceil x⌈d1toti⌉ 枚举 d d d,计算分组个数求分组最小值即可,复杂度为 O ( m n ∗ c n t ) O(mn*cnt) O(mn∗cnt)
得到 K 个半回文串的最少修改次数
数据只有200想法是纯暴力 令 M i n T i m e s [ i ] [ j ] MinTimes[i][j] MinTimes[i][j]为子串 s t r i j str_{ij} strij变成半回文串最少的次数暴力计算复杂度为 O ( n 4 ) O(n^4) O(n4) 令dp[i][j]为以 s t r i str_i stri为结尾时分为 j j j段最少的操作次数 d p [ i ] [ j ] min d p [ z ] [ j − 1 ] M i n T i m e s [ z 1 ] [ i ] dp[i][j] \min dp[z][j-1]MinTimes[z1][i] dp[i][j]mindp[z][j−1]MinTimes[z1][i] 总复杂度 O ( n 4 ) O(n^4) O(n4) 计算MinTimes时可以将一个n优化成 n \sqrt n n 甚至预处理成 lg n \lg n lgn但是 O ( n 4 ) O(n^4) O(n4)也能过就是了,大概是数据比较弱吧
class Solution {
public:int MinTimes[210][210];int dp[210][210];int calTimes(string s,int l,int r){int ret (130);int len r-l1;while(--len){if((r-l1)%len)continue;int ans 0;for(int i0;ilen;i){string t1;for(int jli;jr;jlen)t1 s[j];for(int c0;ct1.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 i0;il;i){for(int ji1;jl;j){MinTimes[i][j] calTimes(s,i,j);}MinTimes[i][i] (130);}for(int i0;il;i){for(int j0;ji;j){for(int z1;zk;z){dp[i1][z] min(dp[i1][z],dp[j][z-1]MinTimes[j][i]);}}}return dp[l][k];}
};
