求解答一道算法题

[codechaser]

/**

• 给定一个数组及其长度 n，每次在这 n 个数字中选取一个数 x，
• 然后取出数组中值为 x 的所有数，获得的资源是 x*值为 x 的元素个数；
• 同时删去刚好值小于(就是刚好比他小))和大于 x(刚好比他大一点)的所有数；
• 然后开始下一轮，直到数组为空。请问能获得的最大资源是？ */

求问这道题怎么做？

[geelaw]

最直接的思路是区间动态规划，自然需要的时间是 n^3，空间是 n^2。
稍微思考可以只考虑开头的区间，时间是 nlogn，额外空间是 1。

具体做法留作习题。

[yidinghe]

看不懂，数组为 [1] 的话，删除比 1 小和比 1 大的数之后，还剩下 [1] ，岂不是永远不会为空？

[Yang2096]

@yidinghe 第二句里面的“取出”大概是先把值为 x 的数全删掉的意思吧

[fxxwor99LVHTing]

没看懂。这是原题吗？
第二句，‘获得的资源是 x*值为 x 的元素个数’ 中 ‘x*值’ 是什么意思？（第二句可能是病句）
第三句中的 ‘刚好’ 具体是什么意思呢？数组中的元素全部由整数组成，还是也可以允许浮点数？

[yidinghe]

唉，理科生的表达能力

[RecursiveG]

把原数组预处理成两个长度为 k 的数组 a[i=1..k]:=第 i 大的数，b[i=1..k]:=a[i]出现的次数。然后从 1 到 k 做 DP。没有证明，不保证对。

[brainfxxk]

@geelaw
@RecursiveG
请教下，按 w[i]=（值*次数）并按值排序预处理之后。假设此序列为 w 长度为 m，操作数次数为 m/3。则我可以从 w 中取任意 m/3 个元素，只要不取首尾两个元素且取到的元素在 w 中不相邻即可对吗？

[zjsxwc]

动态规划，
由于与数组顺序无关于是可以，定义 数组解 A 为 X(n)+ Y(m)+... 其中 X、Y 为数组里数的值，n、m 为数 X、Y 分别出现的次数。

于是状态转移方程为
A(XnYm)=max(X*n-m+A(Ym), Y*m-n+A(Xm))
...
依次类推

[codechaser]

@fxxwor99LVHTing 比如 1 3 4 5 3 6 4 3，这个第一次我取 3，里面有两个 4，那么这次的资源值最大是 4*4，，然后把 4，3 和 5 全去掉，只剩下了 1，6 了，在继续取，这时就取 6，把 1 去掉。总得资源是 4*4+6

[codechaser]

打错了，第一个应该是 3*3，不是 4*4，有三个 3 和两个 4，选 3*3 而不选 4*2。再去掉 3 和 5，只剩 1 6

[codechaser]

@yidinghe 理解一下，这题当时做笔试的时候是一大段文字，我做的时候随手记的。

[zjsxwc]

动态规划，
由于与数组顺序无关于是可以，定义 数组解为 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))
...
依次类推

[codechaser]

@fxxwor99LVHTing 刚好就是说在这个数组里比你取出的元素正好大的。

[zjsxwc]

@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 等大神解答吧

回复：

[codingBug]

瑟瑟发抖

[Vegetable]

@yidinghe 求别黑理科生表达能力吧,理科生描述个题目应该是清清楚楚才对

[RecursiveG]

接 #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])

[RecursiveG]

更正 #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])

[wolfish]

其实就是一个普通 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])

[no1xsyzy]

@brainfxxk #7 只需要不相邻，个数无限制，最多可以 ceiling(n/2)

[layorlayor]

对于一个数 x, 它有 cx 个。比他小的最大数是 y，有 cy 个。比他大的最小数是 z,有 cz 个。 那是不是按照 x * cx - y * cy - z * cz 降序，然后一个一个挑？

[brainfxxk]

@no1xsyzy 个数为什么没限制，每次操作会删掉 3 个元素呀。

[no1xsyzy]

@brainfxxk 不一定，如果删的是两头的只会删掉两个，如果最后只剩一个只会删掉一个

[brainfxxk]

@no1xsyzy 啊是的，也就是如果删除的元素不一定需要有前驱和后继，那么总长度也不需要满足 3 的倍数了。

[BiteTheDust]

首先可以发现原序列没有用
我们把每个值来排序 然后根据每个值的出现次数 使得这个值获得一个权值 得到一个新的序列
显然对于这个新序列 我们不能连续地去取里面的值(也就是说我们取了某个数 就不能取相邻的数)
这样转化后我们就可以用动态规划来获得最大的总和 如果值域不大复杂度可以达到 O(n) 否则复杂度瓶颈为 nlogn 的排序

[nvioue]

不知所云 上 leetcode 链接吧 求你了

[codechaser]

@nvioue 题目的意思就是给出一个数组，你每次可以选择一个值 x，先删除数组中值为 x 的所有元素，用被删除元素个数 n_x 乘以 x 当做这次拿到的资源值，然后删去数组中正好比 x 大和 x 小的所有元素（如[2,4,4,1,5,3,6,3]，x 选 6 的话，总共要删去 6,4,4 这几个元素，资源值为 6。）这样算一次操作，若干次操作后数组会空，问加在一起最大能拿到多少资源值？我不知道这个 leetcode 上有不，这是笔试题，当时就随手记了一下。

[no1xsyzy]

@nvioue 简单地说：
Given X: uint[], n = len(X)
Require x in X while len(X) > 0
Do
X.remove(x)
X.remove(min(a for a in X if a > x))
X.remove(max(a for a in X if a < x))