如何做企業(yè)網(wǎng)站宣傳百度掃一掃網(wǎng)頁版
今日復(fù)習(xí)內(nèi)容：做題
例題1：藍(lán)橋騎士
問題描述：
小藍(lán)是藍(lán)橋王國的騎士，他喜歡不斷突破自我。
這天藍(lán)橋國王給他安排了N個對手，他們的戰(zhàn)力值分別為a1,a2,...,an，且按順序阻擋在小藍(lán)的前方。對于這些對手小藍(lán)可以選擇挑戰(zhàn)，也可以選擇避戰(zhàn)。
身為高傲的騎士，小藍(lán)從不走回頭路，且只愿意挑戰(zhàn)戰(zhàn)力值越來越高的對手。
請你算算小藍(lán)最多會挑戰(zhàn)多少名對手？
輸入描述：
輸入第一行包括一個整數(shù)N，表示對手的個數(shù)；
第二行包括N個整數(shù)：a1,a2,...an，表示每個騎士的戰(zhàn)力值；
1 <= N <= 3*10^5，1 <= ai <= 10^9。
輸出描述：
輸出一行整數(shù)表示答案。
參考答案：
import bisect
n = int(input())
a = list(map(int,input().split()))
q = [a[0]]
for i in range(1,n):ind = bisect.bisect_left(q,a[i])if ind == len(q):q.append(a[i])else:q[ind] = a[i]
print(len(q))運行結(jié)果：
?
以下是我對此題的理解：
首先，從輸入中獲取對手的個數(shù)和每個對手的戰(zhàn)力值；
創(chuàng)建一個空列表q，用于存儲已經(jīng)被挑戰(zhàn)過的對手的戰(zhàn)力值；
從第一個對手開始，遍歷到最后一個對手，依次進(jìn)行以下操作：
使用二分查找在列表q中找到小于等于當(dāng)前對手戰(zhàn)力值的最大值的索引；
如果找到的索引等于q的長度，說明當(dāng)前對手的戰(zhàn)力值大于當(dāng)前已經(jīng)挑戰(zhàn)過的所有對手的戰(zhàn)力值，將當(dāng)前對手的戰(zhàn)力值加入q中，否則，說明當(dāng)前對手的戰(zhàn)力值可以替換q中某個已經(jīng)挑戰(zhàn)過的對手的戰(zhàn)力值，最后輸出q的長度就可以了。
例題2：最長公共子序列
問題描述：
給定一個長度為N的數(shù)組a和一個長度為M的數(shù)組b，請你求出它們的最長公共子序列。
輸入描述：
輸入第一行包括兩個整數(shù)N和M，分別表示數(shù)組a的長度和數(shù)組b的長度。
第二行輸入包含N個整數(shù)a1,a2,...,an；
第三行包含M個整數(shù)b1,b2,...bm；
1 <= N,M <= 10^3,1 <= ai,bi <= 10^9
輸出描述：
輸出一行整數(shù)表示答案
參考答案：
a,b = map(int,input().split())
A = [0] + list(map(int,input().split()))
B = [0] + list(map(int,input().split()))
f = [[0]*(b + 1)for i in range(a + 1)]
for i in range(1,a + 1):for j in range(1,b + 1):if A[i] == B[j]:f[i][j] = f[i-1][j-1] + 1else:f[i][j] = max(f[i-1][j],f[i][j-1])print(f[a][b])運行結(jié)果：
?
這道題用的是動態(tài)規(guī)劃，比較簡單，我就不做過多解釋了。
例題3：倒水
問題描述：
小秋家里來了n位客人，編號為1，2，...，n，現(xiàn)在小秋要給每個客人倒水。
每個客人都有一個滿意度，對于第i個客人，滿意度是這樣定義的：
如果小秋給第i個客人倒了ai毫升水，客人的滿意度為bi；如果小秋給第i個客人倒了ci(ci > ai)毫升水，客人的滿意度為di；
如果小秋給第i為客人倒的水不足ai毫升（也可以為0），客人的滿意度為ei。
現(xiàn)在小秋有m毫升水，請問他要怎么倒水，才能讓所有客人的滿意度之和最大呢？你只需要求出所有客人的滿意度之和的最大值。
輸入描述：
第一行輸入兩個正整數(shù)n和m，表示客人的數(shù)量和小秋所擁有的水的體積；
接下來n行，每行5個整數(shù)ai,bi,ci,di,ei，第i行表示給第i位客人倒了ai毫升水的滿意度為bi，給第i位客人倒了ci毫升水的滿意度為di，倒水不足ai毫升水的滿意度為ei。
輸出格式：
輸出僅一行，包含一個整數(shù)，表示所有課滿意度之和的最大值。
參考答案：
import os
import sys
n,m = map(int,input().split())
f = [[0]*(m + 1) for i in range(n + 1)]
for i in range(1,n + 1):a,b,c,d,e = map(int,input().split())for j in range(m + 1):f[i][j] = f[i - 1][j] + eif j >= a:f[i][j] = max(f[i][j],f[i - 1][j - a] + b)if j >= c:f[i][j] = max(f[i][j],f[i - 1][j - c] + d)
print(f[n][m])運行結(jié)果：
?
以下是我對此題的理解：
我就不寫成文字了，我把注釋過的代碼粘貼過來：
import os
import sys# 輸入客人數(shù)量n和水的體積m
n, m = map(int, input().split())# 初始化動態(tài)規(guī)劃數(shù)組f，f[i][j]表示考慮前i個客人，倒水體積為j時的最大滿意度之和
f = [[0] * (m + 1) for i in range(n + 1)]# 遍歷每位客人
for i in range(1, n + 1):# 獲取當(dāng)前客人的倒水參數(shù)a, b, c, d, e = map(int, input().split())# 遍歷可能的倒水體積for j in range(m + 1):# 初始化當(dāng)前狀態(tài)為上一個狀態(tài)加上當(dāng)前客人倒水不足ai毫升時的滿意度eif[i][j] = f[i - 1][j] + e# 如果當(dāng)前剩余水量j大于等于ai，即可以倒ai毫升水給當(dāng)前客人if j >= a:# 嘗試用當(dāng)前水量j減去ai毫升水，然后加上當(dāng)前客人倒水a(chǎn)i毫升時的滿意度bi，與之前狀態(tài)f[i-1][j-ai]相比較，取最大值f[i][j] = max(f[i][j], f[i - 1][j - a] + b)# 如果當(dāng)前剩余水量j大于等于ci，即可以倒ci毫升水給當(dāng)前客人if j >= c:# 嘗試用當(dāng)前水量j減去ci毫升水，然后加上當(dāng)前客人倒水ci毫升時的滿意度di，與之前狀態(tài)f[i-1][j-ci]相比較，取最大值f[i][j] = max(f[i][j], f[i - 1][j - c] + d)# 輸出考慮了所有客人和水量為m時的最大滿意度之和
print(f[n][m])
?例題4:盜墓分贓2
問題描述：
在一個探險者的團(tuán)隊中，小明和小紅是合伙的盜墓賊。
他們成功盜取了一座古墓中的寶藏，其中包括n件不同重量的寶貴文物和黃金，第i件寶藏的重量為ai。
現(xiàn)在，他們希望公平地分配這些寶藏，使得小明所分得的寶藏的總重量等于小紅所分得的寶藏的總重量。
請檢查是否存在這樣的分配方案，需要注意的是，不能對寶藏進(jìn)行切割來平分重量，只能整個寶藏進(jìn)行分配。
輸入格式：
第一行包含一個正整數(shù)n，表示有n件寶藏；
接下來n行，第i行表示第i件寶藏的重量ai。
輸出格式：
如果能公平分配就輸出yes，否則輸出no。
參考答案：
def work():n = int(input())aa = [0] + [int(input())for i in range(n)]tot = sum(aa)if tot % 2 != 0:print('no')returntot //= 2f = [[False]*(tot + 1) for i in range(n + 1)]f[0][0] = Truefor i in range(1,n + 1):for j in range(tot + 1):f[i][j] = f[i - 1][j]if j >= aa[i]:f[i][j] = f[i - 1][j - aa[i]]print('yes')if f[n][tot] else print('no')
if __name__ == '__main__':work()運行結(jié)果：
?
?第一種做法有一個樣例顯示超時了，所以我優(yōu)化了一下。
第二種做法：
def work():n = int(input())aa = [0] + [int(input())for i in range(n)]tot = sum(aa)if tot % 2 != 0:print('no')returntot //= 2f = [False]*(tot + 1)f[0] = Truefor i in range(1,n + 1):for j in range(tot,aa[i] - 1,-1):f[j] = f[j - aa[i]]print('yes')if f[tot] else print('no')
if __name__ == '__main__':work()以下是我對此題的理解：
我用代碼注釋來表達(dá)我的思想：
def work():# 輸入寶藏的數(shù)量nn = int(input())# 獲取每件寶藏的重量并存儲在列表aa中aa = [0] + [int(input()) for i in range(n)]# 計算所有寶藏的總重量tot = sum(aa)# 如果總重量為奇數(shù)，則無法公平分配，輸出'no'并返回if tot % 2 != 0:print('no')return# 將總重量除以2，得到每個人應(yīng)分得的寶藏的總重量tot //= 2# 創(chuàng)建一個布爾型數(shù)組f，f[i]表示是否存在一種方案使得寶藏的總重量為if = [False] * (tot + 1)# 初始化f[0]為True，表示當(dāng)沒有寶藏時，總重量為0f[0] = True# 遍歷每件寶藏for i in range(1, n + 1):# 從總重量到當(dāng)前寶藏重量之間的位置開始遍歷for j in range(tot, aa[i] - 1, -1):# 如果存在一種分配方案使得總重量為j的話，那么也一定存在一種分配方案使得總重量為j + 寶藏重量f[j] = f[j - aa[i]]# 判斷是否存在一種分配方案使得總重量為tot，如果存在，則輸出'yes'，否則輸出'no'print('yes') if f[tot] else print('no')if __name__ == '__main__':work()
OK，今天狀態(tài)不錯，這幾個題還好，下一篇繼續(xù)！?