求解答一道算法题

[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)