9-9 携程的笔试题

1.文件路径，模拟操作就可以通过

def func1():
    n=int(input())
    dirlist=[]
    for i in range(n):
        dir=input()
        dirlist.append(dir)
    basedir="\\"
    for i in dirlist:
        command=i.strip().split()
        if command[0]=="cd":
            if command[1]=="..":
                index=len(basedir)-1
                while index>0:
                    if basedir[index]=="\\":
                        basedir=basedir[:index]
                        break
                    index-=1
            elif command[1]==".":
                pass
            else:
                basedir+="\\"+command[1]
        elif  command[0]=="pwd":
            if len(basedir[1:])==0:
                print("\\")
            else:
                print(basedir[1:])

2.数组分割 ，不知道怎么写，只会用暴力解，求大佬指点一下

def func2():
    n, k = [int(i) for i in input().split()]
    numlist = [int(i) for i in input().split()]
    from itertools import combinations
    def calc(numlist, n, k):
        res=max(numlist)
        if k >= n:
            return 0
        chioce=combinations([i for i in range(1,n)],k-1)
        for one in chioce:
            temp=cut(list(one),numlist,n)
            if temp<res:
                res=temp
        return res
    def cut(pos,nums,n):
        pos=[0]+pos+[n]
        res=[]
        for i in range(1,len(pos)):
            temp=nums[pos[i-1]:pos[i]]
            res.append(max(temp)-min(temp))
        return max(res)
    print(calc(numlist, n, k))

3.连续1的分割问题， 完全背包问题看到这一点也不算难

n, l = [int(i) for i in input().split()]
string = input()
w = [0]
v = [0]
for i in range(l):
    key, val = [int(i) for i in input().split()]
    w.append(key)
    v.append(val)
def maxsorce(string):
    start = 0
    res = 0
    n = len(string)
    while start < n:
        while start < n and string[start] == "0":
            start += 1
        if start == n:
            return res
        end = start
        while end < n and string[end] == "1":
            end += 1
        res += calc(end - start)
        start = end
    return res

def calc(weight):
    global w, v
    n = len(w)-1
    dp = [[0] * (weight + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        # 0-1 背包的话从后往前进行计算， 因为每一个就会计算一次
        for j in range(weight + 1):
            if j < w[i]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i])
    return dp[n][weight]
print(maxsorce(string))