网站推广和优化系统海宁做网站

网站推广和优化系统,海宁做网站,讯代理网站,网站建设所用软件3836.恰好K个下标对的最大得分难度#xff1a;困难问题描述#xff1a;给你两个长度分别为n和m的整数数组nums1和nums2#xff0c;以及一个整数k。你必须恰好选择k对下标(i1,j1),(i2,j2),...,(ik,jk)#xff0c;使得#xff1a;0i1i2...ikn0j1<…3836.恰好K个下标对的最大得分难度困难问题描述给你两个长度分别为n和m的整数数组nums1和nums2以及一个整数k。你必须恰好选择k对下标(i1,j1),(i2,j2),...,(ik,jk)使得0i1i2...ikn0j1j2...jkm对于每对选择的下标(i,j)你将获得nums1[i]*nums2[j]的得分。总得分是所有选定下标对的乘积的总和。返回一个整数表示可以获得的最大总得分。示例1:输入nums1[1,3,2],nums2[4,5,1],k2输出22解释一种最优的下标对选择方案是(i1,j1)(1,0)得分为3*412(i2,j2)(2,1)得分为2*510总得分为121022。示例2:输入nums1[-2,0,5],nums2[-3,4,-1,2],k2输出26解释一种最优的下标对选择方案是(i1,j1)(0,0)得分为-2*-36(i2,j2)(2,1)得分为5*420总得分为62026。示例3:输入nums1[-3,-2],nums2[1,2],k2输出-7解释最优的下标对选择方案是(i1,j1)(0,0)得分为-3*1-3(i2,j2)(1,1)得分为-2*2-4总得分为-3(-4)-7。提示1nnums1.length1001mnums2.length100-106nums1[i],nums2[i]1061kmin(n,m)问题分析因为从n个元素的数组中选k个元素不好确定它们的顺序所以采用从n个序列号中选k个序列号来处理这样通过序列号既方便控制元素顺序也方便提取原数组中的元素值。处理步骤如下先找到从n个元素的数组中取出k个元素的全排列方法函数get_k_from_n(a,k)实现这一功能其中参数a是包含n个序列号的数组k为选取的个数函数choose_subscript_array(n,k)通过调用get_k_from_n(a,k)实现从0至n-1的序列号中选取k个升序序列号的功能将n和m及k传入choose_subscript_array(n,k)生成与nums1和nums2各自对应的序列号序列主程序通过二重循环让与nums1和nums2对应的序列号配对并计算得分最后将其中最大得分输出即为问题的解。程序如下#从n个数中选择k个共有多少种选法 def get_k_from_n(a,k): nlen(a) if k2: t[] for i in range(n-1): for j in range (i1,n): t.append([a[i],a[j]]) return t else: t[] for i in range(n): lefta[:i] righta[i1:] tempget_k_from_n(leftright,k-1) for j in temp: t.append([a[i]]j) return t #从n个下标中生成k个下标序列并返回 def choose_subscript_array(n,k): a list(range(n)) b get_k_from_n(a, k) b list(sorted(i) for i in b) t [] for i in b: if i not in t: t.append(i) return t #主程序 nums1eval(input(pls input nums1)) nums2eval(input(pls input nums2)) kint(input(pls input k)) nlen(nums1) mlen(nums2) achoose_subscript_array(n,k) bchoose_subscript_array(m,k) d_sum0 for x in range(k): d_sum nums1[a[0][x]] * nums2[b[0][x]] sum_maxd_sum sna[0] smb[0] for i in a: for j in b: d_sum 0 for x in range(k): d_sumnums1[i[x]]*nums2[j[x]] if d_sumsum_max: sum_maxd_sum sni smj print(最优的下标对选择方案是) clist(zip(sn,sm)) for i in range(k): print(f(i{i}, j{i}) {c[i]}得分为 {nums1[c[i][0]]} *{nums2[c[i][1]]} {nums1[c[i][0]] *nums2[c[i][1]]}) print(f可以获得的最大总得分为{sum_max})运行实例一pls input nums1[1,3,5,8]pls input nums2[2,1,3]pls input k3最优的下标对选择方案是(i0, j0) (1, 0)得分为 3 *2 6(i1, j1) (2, 1)得分为 5 *1 5(i2, j2) (3, 2)得分为 8 *3 24可以获得的最大总得分为35运行实例二pls input nums1[1,8,2,10,7]pls input nums2[3,9,10,8]pls input k3最优的下标对选择方案是(i0, j0) (1, 1)得分为 8 *9 72(i1, j1) (3, 2)得分为 10 *10 100(i2, j2) (4, 3)得分为 7 *8 56可以获得的最大总得分为228运行实例三pls input nums1[3,4,2]pls input nums2[5,6,7]pls input k3最优的下标对选择方案是(i0, j0) (0, 0)得分为 3 *5 15(i1, j1) (1, 1)得分为 4 *6 24(i2, j2) (2, 2)得分为 2 *7 14可以获得的最大总得分为53