公司网站域名如何备案,app开发网站建设哪家好,网络推广应该怎么做啊,生鲜市场型网站开发原题链接力扣 题目大意#xff1a;我开始看成连续子段了#xff0c;写了个递归程序.......
一个数组任选一个子序列#xff0c;子序列的力量值最大值平方*最小值。求所有子序列的力量和。
分析过程#xff1a;如序列长度为n#xff0c;子序列总数为2的n次幂#xff0c…原题链接力扣 题目大意我开始看成连续子段了写了个递归程序.......
一个数组任选一个子序列子序列的力量值最大值平方*最小值。求所有子序列的力量和。
分析过程如序列长度为n子序列总数为2的n次幂显然不可能枚举所有子序列来求解。那么只能锁定子序列最大值和最小值来处理。容易想到先排序排序后的序列可以取任意ai和aj那么ai最小值aj 最大值,i和j之间的元素可以任取例如i2j6那么i和j之间有3个其他元素这3个元素可以任取因此共有2的3次幂共8种选取方法(a2,a6) (a2,a3,a6) (a2,a4,a6) (a2,a5,a6)a2,a3,a4,a6.......。枚举所有i和j时间复杂度为O(n2)。
这类问题如何继续降低复杂度。一般来说都会存在某种规律使得下一次的处理能利用上一次的结果也有写问题存在某种数学方法能直接求得解。本题目通过找规律解决。
假设a1为最小值那么子序列中必然有a1此时如果锁定ai为最大值那么所有满足a1最小ai最大的子序列数量必然ai*ai*a1*pow(2,i-2)。
枚举下最大最小值分别为(i,j的公式
最大值j\最小值ia1 a2a3......总和a2a1*a2*a2 (a1)*a2*a2 a32a1*a3*a3a2*a3*a3 2a1a2*a3*a3 a44a1*a4*a42a2*a4*a44a12a2a3*a4*a4a58a1*a5*a54a2*a5*a52a3*a5*a5......8a14a22a3a4*a5*a5a616a1*a6*a68a2*a6*a64a3*a6*a6......
可以发现规律为当ai为最大值时其组成所有子序列的力量和为Y[i]*a[i]*a[i]而这个Y[i]可以由Y[i-1]*2a[i-1]求得。
class Solution {
public:int sumOfPower(vectorint nums) {int i,j,rnums.size()-1mod1e97;;sort(nums.begin(),nums.end());/** 排序 */long long ans0,sumnums[0];for(i0;ir;i)/** 就一个元素序列单独处理 */ans(ans1LL*nums[i]*nums[i]%mod*nums[i])%mod;for(i1;ir;i)/** 最大值为i的力量和 */{long long temp1LL*nums[i]*nums[i]%mod;ans(anstemp*sum%mod)%mod;sum(sum*2nums[i])%mod;/** i1的系数 */}return (int)ans;}
};两个循环综合在一起的写法。
class Solution {
public:int sumOfPower(vectorint nums) {int i,j,rnums.size()-1,mod1e97;;sort(nums.begin(),nums.end());/** 排序 */long long ans0,sum0;for(i0;ir;i)/** 最大值为i的力量和 */{long long temp1LL*nums[i]*nums[i]%mod;ans(anstemp*(sumnums[i])%mod)%mod;sum(sum*2nums[i])%mod;/** i1的系数 */}return (int)ans;}
};
