分金子（360公司2017春招真題）

題目鏈接

https://exercise.acmcoder.com/online/online_judge_ques?ques_id=3863&konwledgeId=42
可以去鏈接里看一看，不再贅述題目了，

解題思路

假設幾個變數，f(i,j)是從[i，j]中可以拿到的最大價值，因為只可以從兩端拿，假如先手是從最左端拿的，那剩下的最大價值就是f(i+1,j)，也就是后手能拿到的最大價值；那先手能拿到的最大價值可以用sum(i,j)-f(i+1,j)來表示，
假如先手是從最右端拿的，剩下最大價值就是f(i,j-1)，也就是后手能拿到的最大價值；那先手能拿到的最大價值可以用sum(i,j)-f(i,j-1)來表示，
那究竟應該從哪邊拿，當然是看f(i+1,j)和f(i,j-1)的大小，最后可以提煉出

f(i,j) = max{(sum(i,j)-f(i+1,j)),sum(i,j)-f(i,j-1)} = sum(i,j)-min{f(i+1,j),f(i,j-1)}

代碼實作

遞回版

從上式可以看出，遞回是一種解決方案，為了避免重復計算，使用一個變數來記錄算出來的f(n,m)的值，

def digui(lst,i,j):
    if(i==j):
        return lst[i]
    elif(res[i][j]!=0):
        return res[i][j]
    else:
        res[i][j]=sum(lst[i:j+1])-min(digui(lst,i+1,j),digui(lst,i,j-1))
        return res[i][j]

n=int(input())
for q in range(n):
    num=int(input())
    res = [[0]*(num+1) for i in range(num+1)]
    lst=list(map(int,input().split()))
    lst=[0]+lst
    a=digui(lst,1,num)
    b=sum(lst)-digui(lst,1,num)
    print("Case #%s: %s %s"%(q+1,a,b))

動態規劃版

我也說不上來什么叫做動態規劃，總之大家都是這樣叫的，當初看別人代碼時，也是一臉懵比，然后自己整個手推了一遍，豁然開朗，
我們使用給的案例

4 7 2 9 5 2

上面是一列金子，先畫一張表，為了方便表示，我們從1開始，0列0行都當作是空白

‘’	0	1	2	3	4	5	6
0	‘’	‘’	‘’	‘’	‘’	‘’	‘’
1	‘’	‘’	‘’	‘’	‘’	‘’	‘’
2	‘’	‘’	‘’	‘’	‘’	‘’	‘’
3	‘’	‘’	‘’	‘’	‘’	‘’	‘’
4	‘’	‘’	‘’	‘’	‘’	‘’	‘’
5	‘’	‘’	‘’	‘’	‘’	‘’	‘’
6	‘’	‘’	‘’	‘’	‘’	‘’	‘’

接下來可以填表了，假如是從[1,1]取，那就一種取法，就是該位置上的數量，其他只有一個金子的情形也是這樣，填表，

‘’	0	1	2	3	4	5	6
0	‘’	‘’	‘’	‘’	‘’	‘’	‘’
1	‘’	4	‘’	‘’	‘’	‘’	‘’
2	‘’	‘’	7	‘’	‘’	‘’	‘’
3	‘’	‘’	‘’	2	‘’	‘’	‘’
4	‘’	‘’	‘’	‘’	9	‘’	‘’
5	‘’	‘’	‘’	‘’	‘’	5	‘’
6	‘’	‘’	‘’	‘’	‘’	‘’	2

那如果是[1,2]該怎么取呢，公式交給我們，應該是先得到[1,2]的和，然后減去較小的那個，那[2,3],[3,4]也是類似，

‘’	0	1	2	3	4	5	6
0	‘’	‘’	‘’	‘’	‘’	‘’	‘’
1	‘’	4	7	‘’	‘’	‘’	‘’
2	‘’	‘’	7	7	‘’	‘’	‘’
3	‘’	‘’	‘’	2	9	‘’	‘’
4	‘’	‘’	‘’	‘’	9	9	‘’
5	‘’	‘’	‘’	‘’	‘’	5	5
6	‘’	‘’	‘’	‘’	‘’	‘’	2

規律很明顯了，接著填表即可，最后表的狀態如下，

‘’	0	1	2	3	4	5	6
0	‘’	‘’	‘’	‘’	‘’	‘’	‘’
1	‘’	4	7	6	16	11	18
2	‘’	‘’	7	7	11	16	24
3	‘’	‘’	‘’	2	9	7	11
4	‘’	‘’	‘’	‘’	9	9	11
5	‘’	‘’	‘’	‘’	‘’	5	5
6	‘’	‘’	‘’	‘’	‘’	‘’	2

那[1,6]最大的收益就是1行6列的18了，后面只需要交給計算機來幫我們填表即可，

n=int(input())
for q in range(n):
    num=int(input())
    lst = list(map(int,input().split()))
    res = [[0]*(num+1) for i in range(num+1)]
    for i in range(1,num+1):
        res[i][i] = lst[i-1]
    cnt=1
    while cnt<=num:
        i=1
        j=i+cnt
        while j<=num:
            res[i][j] = sum(lst[i-1:j]) - min(res[i][j-1],res[i+1][j])
            i+=1
            j+=1
        cnt+=1
    a = res[1][num]
    b = sum(lst) - a
    print("Case #%s: %s %s"%(q+1,a,b))

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/69639.html

標籤：其他

上一篇：最小生成樹（Prim和Kruscal）

下一篇：反素數決議

動態規劃刷題

分金子（360公司2017春招真題）

題目鏈接

解題思路

代碼實作

遞回版

動態規劃版