[已解决]Python：每日一题 271

阴阳神万物主

诶？楼主，我突然想到了一个点子，就是：在每日一题的高亮期限结束的时候，如果还没有人通过，能不能劳烦楼主您受累，发布一个题解什么的，讲解代码顺便再讲解题目。若有精力，可以选择性地摘一些出错的典型，指出它们的毛病。

WXF666

n！个结果，太难了。。。

fish_b

版主大大可不可以给一个长的数组，和它的答案呀，想要拿来自己验证一下，谢谢

fish_b

发现不对，改下代码

爱尔兰咖啡

def f0(x):
        #计算最小值气球爆炸的所有乘积，放入lst0,不含最小值的用'*'填充
        lst0=[]
        y=x[1:-1]
        #找出最小值min1
        min1=min(y)
        n=len(y)
        for i in range(n):
                if y[i]==min1:
                        lst0.append(x[i]*x[i+1]*x[i+2])
                else:
                        lst0.append('*')
        #为方便操作，lst0首尾填充'*'
        lst0.insert(0,'*')
        lst0.append('*')
        print(lst0)
        #删除lst0的所有'*',形成lst1
        lst1=filter(lambda x:x!='*',lst0)
        lst1=list(lst1)
        print(lst1)
        #找出lst1的最大值m0
        m0=max(lst1)
        #找出m0在lst0的index，n
        n=lst0.index(m0)
        #将x的第n个值删除,形成新x
        x=x[:n]+x[n+1:]
        #返回x,m0
        return x,m0
def f1(x):
        #求和s
        n=len(x)
        if n==1:s=x[0]
        if n==2:s=x[0]*x[1]+max(x)
        if n>=3:
                m=n-2
                s=0
                for i in range(m):
                        x,m0=f0(x)
                        s+=m0
                s=s+x[0]*x[1]+max(x)
        print(s)
        return s
def main():
        f1([4,1,5,10])
if __name__=='__main__':
        main()

爱尔兰咖啡

都是高手

Unicorn#

想了很久，似乎没有找到好的思路
这里添加了记忆化搜索，优化了很多。因为重复遍历次数实在太多了
尽力了

def solve(nums):
    while 0 in nums:
        nums.remove(0)
    record = {}
    def f(nums):
        if str(nums) in record:
            return record[str(nums)]
        elif len(nums) == 0:
            return 0
        else:
            temp = max(f(nums[:i]+nums[i+1:])+(nums[i-1]if i >= 0 else 1)*nums[i]*(nums[i+1]if i+1 < len(nums) else 1)for i in range(len(nums)))
            record[str(nums)] = temp
            return temp
    return f(nums)

Stubborn

from typing import List
def IntervalDp(nums:List[int]):
    """
    dp从子问题推导到父问题：由小区间，推导到大区间

    定义dp[i][j]表示爆掉i至j个气球最优解(包含i和j在内的气球)
    nums = [4, 1, 5, 10]，以从至右任意一个位置k为例。Ps:边界使用1填充[1,4, 1, 5, 10,1]
    初始化数组：dp = [[0]* len(nums) for _ in range(len(nums))]
        假设K为最后一个气球，我们可以获得的分数为：
            nums[左:k] + nums[左-1] * nums[k] * nums[右-1] + nums[k:右]
            nums[左:k]：爆掉k左侧位置所有气球可以获得的分数
            nums[左-1] * nums[k] * nums[右-1]：爆掉k获得的分数
            nums[k:右]： 爆掉k右侧可以获得的分数
        dp[i][j] = max{
            dp[i][j]
            nums[左-1] * nums[k] * nums[右-1] + nums[左:k] + nums[k:右]
        }
        举例：                当前最优解                k分数+左侧分数 +右侧分数
        dp[0][2] = max { dp[0][2], 1*4*1 + dp[0][1] + dp[1][2]} -> {0, 4 + 0 + 0}
        dp[1][3] = max { dp[1][3], 4*1*5 + dp[1][2] + dp[2][3]} -> {0, 20 + 0 + 0}
        ....
        dp[0][3] = max {dp[0][3], 1*4*5 + dp[0][1] + dp[1][3]}  -> {0, 20 + 0 + 20}
        dp[0][3] = max {dp[0][3], 1*4*1 + dp[0][2]+ dp[2][3]}   -> {40,20 + 0 + 4}
        所以有：
        dp[i][j] = max{
            dp[i][j],
            dp[i][k] + nums[i]*nums[k]*num[j] + dp[k][j]
        }

    """
    if len(nums) == 0: return 0
    if len(nums) == 1: return nums[0]
    if len(nums) == 2: return nums[0] * nums[1] + max(nums)

    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    for k in range(2, n):
        for left in range(n - k):
            right = left + k
            for i in range(left + 1, right):
                dp[left][right] = max(
                    dp[left][right],
                    dp[left][i] + nums[left] * nums[i] * nums[right] + dp[i][right]
                )
    return dp[0][-1]

zltzlt

danteer 发表于 2019-11-9 18:40

输入 [35,16,83,87,84,59,48,41,20,54] 超时

zltzlt

fish_b 发表于 2019-11-9 20:55
版主大大可不可以给一个长的数组，和它的答案呀，想要拿来自己验证一下，谢谢

输入：[42,23,62,2,89,97,26,82,47,23,9,2,9,11,53,49,40,3,88,76,63,11,79,37,52,91,5,44,71,69,20,5,74,41,70,68,26,16,62,53,47,46,26,27,99,72,4,40,77,74,89,19,26,7,30,79,49,75,51,28,47,26,55,81,82,15,21,89,51,10,0,50,31,32,38,7,99,13,23,98,68,9,54,15,34,52,58,48,66,75,6,15,91,33,15,37,25,98,98,77,60,16,82,89,48,43,1,85,39,99,95,86,45,90,73,45,93,99,39,57,32,47,35,79,25,54,98,34,60,90,38,40,5,5,96,21,18,93,69,38,85,49,15,77,84,70,52,87,73,15,65]
输出：53234968

zltzlt

爱尔兰咖啡 发表于 2019-11-9 22:33
def f0(x):
        #计算最小值气球爆炸的所有乘积，放入lst0,不含最小值的用'*'填充
        lst0=[]

输入：[35,16,83,87,84,59,48,41,20,54]
打印：
['*', 46480, '*', '*', '*', '*', '*', '*', '*', '*']
[46480]
['*', '*', '*', '*', '*', '*', '*', 44280, '*']
[44280]
['*', '*', '*', '*', '*', '*', 106272, '*']
[106272]
['*', '*', '*', '*', '*', 152928, '*']
[152928]
['*', '*', '*', '*', 267624, '*']
[267624]
['*', 252735, '*', '*', '*']
[252735]
['*', '*', 394632, '*']
[394632]
['*', 164430, '*']
[164430]
1431325
输出：1431325
预期结果：1849648

zltzlt

Unicorn# 发表于 2019-11-10 00:32
想了很久，似乎没有找到好的思路
这里添加了记忆化搜索，优化了很多。因为重复遍历次数实在太多了
尽力了 ...

解答错误

输入：[4,1,5,10]
输出：820
预期结果：270

zltzlt

Stubborn 发表于 2019-11-10 04:00

恭喜通过！

执行用时：806 ms

zltzlt

华一仙 发表于 2019-11-10 10:31

恭喜通过！

执行用时：705 ms

Unicorn#

zltzlt 发表于 2019-11-10 14:16
解答错误

输入：[4,1,5,10]

多打了一个等号

def solve(nums):
    while 0 in nums:
        nums.remove(0)
    record = {}
    def f(nums):
        if str(nums) in record:
            return record[str(nums)]
        elif len(nums) == 0:
            return 0
        else:
            temp = max(f(nums[:i]+nums[i+1:])+(nums[i-1]if i > 0 else 1)*nums[i]*(nums[i+1]if i+1 < len(nums) else 1)for i in range(len(nums)))
            record[str(nums)] = temp
            return temp
    return f(nums)

阴阳神万物主

爱尔兰咖啡 发表于 2019-11-9 22:33
def f0(x):
        #计算最小值气球爆炸的所有乘积，放入lst0,不含最小值的用'*'填充
        lst0=[]

如何正确地发代码、上传图片和附件？
https://fishc.com.cn/thread-52272-1-1.html
(出处: 鱼C论坛——小甲鱼)

爱尔兰咖啡

def ball(x):
    result=[]
    def f(x,sum=0):
        if len(x)==1:result.append(x[0]+sum)
        if len(x)==2:result.append(x[0]*x[1]+max(x)+sum)
        if len(x)>=3:
            for i in range(1,len(x)-1):
                mul=x[i-1]*x[i]*x[i+1]
                temp=x[:]
                temp.pop(i)
                f(temp,sum+mul)
    f(x)
    return max(result)
a=[4,1,5,10]
b=[3,1,5]
print(ball(a))
print(ball(b))

现学现卖

zltzlt

爱尔兰咖啡 发表于 2019-11-10 14:57
现学现卖

输入 [2,4,8,4,0,7,8,9,1,2,4,7,1,7,3] 超时

zltzlt

Unicorn# 发表于 2019-11-10 14:44
多打了一个等号

输入 [8,2,6,8,9,8,1,4,1,5,3,0,7,7,0,4,2,2,5,5] 超时

Jacques666

def  counts(lists):
        n =int(len(lists))
        m =[]
        for i in range(0,n):
                if i ==0 and i ==i :
                        c= 1*lists[i]*lists[i+1]
                        m.append(c)
                elif i in range(1,n-1):
                        c=lists[i-1]*lists[i]*lists[i+1]
                        m.append(c)
        print(sum(m))

counts([1,2,3,4,5,6])