这是一个创建于 1918 天前的主题，其中的信息可能已经有所发展或是发生改变。
/**
- 给定一个数组及其长度 n，每次在这 n 个数字中选取一个数 x，
- 然后取出数组中值为 x 的所有数，获得的资源是 x*值为 x 的元素个数；
- 同时删去刚好值小于(就是刚好比他小))和大于 x(刚好比他大一点)的所有数；
- 然后开始下一轮，直到数组为空。请问能获得的最大资源是？ */
求问这道题怎么做？
 |
1
geelaw 2019-09-22 21:56:19 +08:00 via iPhone  1
最直接的思路是区间动态规划，自然需要的时间是 n^3，空间是 n^2。
稍微思考可以只考虑开头的区间，时间是 nlogn，额外空间是 1。 具体做法留作习题。 |
 |
2
yidinghe 2019-09-22 22:25:12 +08:00
看不懂，数组为 [1] 的话，删除比 1 小和比 1 大的数之后，还剩下 [1] ，岂不是永远不会为空？
|
 |
4
fxxwor99LVHTing 2019-09-22 23:32:56 +08:00
没看懂。这是原题吗？
第二句，‘获得的资源是 x*值为 x 的元素个数’ 中 ‘x*值’ 是什么意思？（第二句可能是病句） 第三句中的 ‘刚好’ 具体是什么意思呢？数组中的元素全部由整数组成，还是也可以允许浮点数？ |
|
5
yidinghe 2019-09-23 01:22:58 +08:00 via Android
唉，理科生的表达能力
|
 |
6
RecursiveG 2019-09-23 04:47:43 +08:00
把原数组预处理成两个长度为 k 的数组 a[i=1..k]:=第 i 大的数，b[i=1..k]:=a[i]出现的次数。然后从 1 到 k 做 DP。没有证明，不保证对。
|
 |
7
brainfxxk 2019-09-23 05:26:33 +08:00
@geelaw
@RecursiveG 请教下，按 w[i]=（值*次数）并按值排序预处理之后。假设此序列为 w 长度为 m，操作数次数为 m/3。则我可以从 w 中取任意 m/3 个元素，只要不取首尾两个元素且取到的元素在 w 中不相邻即可对吗？ |
 |
8
zjsxwc 2019-09-23 07:29:02 +08:00 via Android
动态规划，
由于与数组顺序无关于是可以，定义 数组解 A 为 X(n)+ Y(m)+... 其中 X、Y 为数组里数的值，n、m 为数 X、Y 分别出现的次数。 于是状态转移方程为 A(XnYm)=max(X*n-m+A(Ym), Y*m-n+A(Xm)) ... 依次类推 |
 |
9
codechaser OP @fxxwor99LVHTing 比如 1 3 4 5 3 6 4 3，这个第一次我取 3，里面有两个 4，那么这次的资源值最大是 4*4，，然后把 4，3 和 5 全去掉，只剩下了 1，6 了，在继续取，这时就取 6，把 1 去掉。总得资源是 4*4+6
|
|
10
codechaser OP 打错了，第一个应该是 3*3，不是 4*4，有三个 3 和两个 4，选 3*3 而不选 4*2。再去掉 3 和 5，只剩 1 6
|
|
11
codechaser OP @yidinghe 理解一下，这题当时做笔试的时候是一大段文字，我做的时候随手记的。
|
|
12
zjsxwc 2019-09-23 07:47:15 +08:00 via Android
动态规划，
由于与数组顺序无关于是可以，定义 数组解为 A(XnYm) 其中 X、Y 为数组里数的值，n、m 为数 X、Y 分别出现的次数。 于是状态转移方程为 A(Xn)=X*n A(XnYm)=max(X*n-m+A(Ym), Y*m-n+A(Xm)) A(XnYmZa)=max(X*n-m-a+A(YmZa), Y*m-n-a+A(XmZa), Z*a-n-mA(XnYm)) ... 依次类推 |
|
13
codechaser OP @fxxwor99LVHTing 刚好就是说在这个数组里比你取出的元素正好大的。
|
|
14
zjsxwc 2019-09-23 07:55:11 +08:00 via Android
@zjsxwc #12 原文：“动态规划，由于与数组顺序无关于是可以，定义 数组解为 A(XnYm) 其中 X、Y 为数组里数的值，n、m 为数 X、Y 分别出现的次数。于是状态转移方程为 A(Xn)=X*nA(XnYm)=max(X*n-m+A(Ym), Y*m-n+A(Xm))A(XnYmZa)=max(X*n-m-a+A(YmZa), Y*m-n-a+A(XmZa), Z*a-n-m+A(XnYm))...依次类推”
感觉复杂度还是 n^3 等大神解答吧 回复： |
 |
15
codingBug 2019-09-23 09:24:42 +08:00
瑟瑟发抖
|
|
17
RecursiveG 2019-09-23 09:45:22 +08:00
接 #6
再令 p[1]:=a[1]*b[1], u[0]:=0 p[1<i<=k]:=u[i-1]+a[1]*b[1] u[1<i<=k]:=max(u[i-1],p[i-1]) 结果为 max(u[k],p[k]) |
|
18
RecursiveG 2019-09-23 09:46:31 +08:00
更正 #17
再令 p[1]:=a[1]*b[1], u[1]:=0 p[1<i<=k]:=u[i-1]+a[i]*b[i] u[1<i<=k]:=max(u[i-1],p[i-1]) 结果为 max(u[k],p[k]) |
 |
19
wolfish 2019-09-23 11:11:49 +08:00
其实就是一个普通 01 背包问题。
假设 n 个数里有 m 种数值，将这 m 种数值从小到大排序，并记每种数值的价值为 val[i]=值本身*个数 i：1~m 然后就是 dp 定义。 dp[i][0]：前 i 种数，不选入第 i 种数值，所获得的最大价值 dp[i][1]：前 i 种数，选入第 i 种数值，所获得的最大价值。 dp[i][0] = max(dp[i-1][0], dp[i-1][1]) dp[i][1] = dp[i-1][0]+val[i] 最终结果就是 max(dp[m][0], dp[m][1]) |
 |
21
layorlayor 2019-09-23 14:43:57 +08:00
对于一个数 x, 它有 cx 个。比他小的最大数是 y，有 cy 个。比他大的最小数是 z,有 cz 个。 那是不是按照 x * cx - y * cy - z * cz 降序，然后一个一个挑？
|
 |
25
BiteTheDust 2019-09-23 20:10:07 +08:00
首先可以发现原序列没有用
我们把每个值来排序 然后根据每个值的出现次数 使得这个值获得一个权值 得到一个新的序列 显然对于这个新序列 我们不能连续地去取里面的值(也就是说我们取了某个数 就不能取相邻的数) 这样转化后我们就可以用动态规划来获得最大的总和 如果值域不大复杂度可以达到 O(n) 否则复杂度瓶颈为 nlogn 的排序 |
 |
26
nvioue 2019-09-24 00:10:23 +08:00 via Android
不知所云 上 leetcode 链接吧 求你了
|
|
27
codechaser OP @nvioue 题目的意思就是给出一个数组，你每次可以选择一个值 x，先删除数组中值为 x 的所有元素，用被删除元素个数 n_x 乘以 x 当做这次拿到的资源值，然后删去数组中正好比 x 大和 x 小的所有元素（如[2,4,4,1,5,3,6,3]，x 选 6 的话，总共要删去 6,4,4 这几个元素，资源值为 6。）这样算一次操作，若干次操作后数组会空，问加在一起最大能拿到多少资源值？我不知道这个 leetcode 上有不，这是笔试题，当时就随手记了一下。
|
Select Language