題目1 01背包

有 N 件物品和一個容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的體積是 vi，價值是 wi。

求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。
輸出最大價值。

輸入格式

第一行兩個整數，N，V，用空格隔開，分別表示物品數量和背包容積。

接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分別表示第 i 件物品的體積和價值。

輸出格式

輸出一個整數，表示最大價值。

數據范圍

0<N,V≤1000
0<vi,wi≤1000

輸入樣例

4 5
1 2
2 4
3 4
4 5

輸出樣例：

8

python代碼

N=1010
n,v=map(int,input().split())
data=[[0,0]]
for i in range(n):a,b=map(int,input().split())data.append([a,b])
dp=[[0 for _ in range(N)]for _ in range(N)]# print(data)
for i in range(1,n+1):for j in range(1,v+1):if data[i][0]>j:dp[i][j]=dp[i-1][j]else:dp[i][j]=max(dp[i-1][j],dp[i-1][j-data[i][0]]+data[i][1])
print(dp[n][v])

知識點

1. 動態規劃，因為需要用到下標i-1,一般下標都是從1開始
2. 背包問題是組合問題的范疇，另外幾個模型是，路線問題、最長上升子序列問題等
3. dp[i][j]含義:從前i個物品中選，總體積不超過j的選法的集合
   • 不選擇第i個物品：等價于dp[i-1][j]
   • 選擇第i個物品：首先看第i個物品的體積是否大于體積，若小于，則比較最終的價值相比 不選更高，若更高，則選擇第i個物品

題目2 摘花生

Hello Kitty想摘點花生送給她喜歡的米老鼠。

她來到一片有網格狀道路的矩形花生地(如下圖)，從西北角進去，東南角出來。

地里每個道路的交叉點上都有種著一株花生苗，上面有若干顆花生，經過一株花生苗就能摘走該它上面所有的花生。

Hello Kitty只能向東或向南走，不能向西或向北走。

問Hello Kitty最多能夠摘到多少顆花生。

輸入格式

第一行是一個整數T，代表一共有多少組數據。

接下來是T組數據。

每組數據的第一行是兩個整數，分別代表花生苗的行數R和列數 C。

每組數據的接下來R行數據，從北向南依次描述每行花生苗的情況。每行數據有C個整數，按從西向東的順序描述了該行每株花生苗上的花生數目M。

輸出格式

對每組輸入數據，輸出一行，內容為Hello Kitty能摘到得最多的花生顆數。

數據范圍

1≤T≤100,
1≤R,C≤100,
0≤M≤1000

輸入樣例：

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

輸出樣例：

8
16
```## python代碼```python
t=int(input())
N=110
while t:r,c=map(int,input().split())data=[[0 for _ in range(c+1)]for _ in range(r+1)]dp=[[0 for _ in range(N)]for _ in range(N)]#初始化狀態for i in range(1,r+1):data[i]=[0]+list(map(int,input().split()))for i in range(1,r+1):for j in range(1,c+1):dp[i][j]=max(dp[i-1][j]+data[i][j],dp[i][j-1]+data[i][j])print(dp[r][c])t-=1

知識點

1. 從第一行開始置換每一行數據：

   for i in range(1,r+1):data[i]=[0]+list(map(int,input().split()))
   

2. dp[i][j]含義:從起點到(i,j)坐標的路線集合，集合劃分為兩類
   • 上一步是從左往右走：等價于dp[i][j-1]
   • 上一步是從上往下走：等價于dp[i-1][j]
3. 集合計算：找到最大值，加上當前數據值data[i][j]

題目3 最長上升子序列

題目描述

這是一個簡單的動規板子題。

給出一個由 $n(n\le 5000)$ 個不超過 $10^6$ 的正整數組成的序列。請輸出這個序列的最長上升子序列的長度。

最長上升子序列是指，從原序列中按順序取出一些數字排在一起，這些數字是逐漸增大的。

輸入格式

第一行，一個整數 $n$，表示序列長度。

第二行有 $n$ 個整數，表示這個序列。

輸出格式

一個整數表示答案。

輸入輸出樣例

輸入

6
1 2 4 1 3 4

輸出

4

說明/提示

分別取出 $1$、$2$、$3$、$4$ 即可。

python代碼

#DP，總是有一組數據超時，拿到80%分數
n=int(input())
data=[0]+list(map(int,input().split()))
# print(data)
N=5010
dp=[0]*(n+1)
for i in range(1,n+1):dp[i]=1for j in range(1,i):if data[j]<data[i]:dp[i]=max(dp[i],dp[j]+1)
print(max(dp))#二分，全部通過
import bisectn=int(input())
data=list(map(int,input().split()))#讀取數據lis=[]#存放
for num in data:pos=bisect.bisect_left(lis,num)if pos==len(lis):lis.append(num)else:lis[pos]=num
# print(lis)
print(len(lis))

知識點

1. dp[i]：所有以i結尾的嚴格上升子序列長度
   • 若data[j]<data[i],可以放在前面，那么dp[i]=dp[j]+1
   • 但是dp[i]>dp[j]+1，那么dp[i]保持
2. pos=bisect.bisect_left(lis,num):在lis中找到不大于num的 下標pos

題目4 買不到的數目

小明開了一家糖果店。

他別出心裁：把水果糖包成4顆一包和7顆一包的兩種。

糖果不能拆包賣。

小朋友來買糖的時候，他就用這兩種包裝來組合。

當然有些糖果數目是無法組合出來的，比如要買 10 顆糖。

你可以用計算機測試一下，在這種包裝情況下，最大不能買到的數量是17。

大于17的任何數字都可以用4和7組合出來。

本題的要求就是在已知兩個包裝的數量時，求最大不能組合出的數字。

輸入格式

兩個正整數 n,m，表示每種包裝中糖的顆數。

輸出格式

一個正整數，表示最大不能買到的糖數。

數據范圍

2≤n,m≤1000，
保證數據一定有解。

輸入樣例：

4 7

輸出樣例：

17

思路

藍橋杯的數學頻率還是很高的，實在不會，就打表找規律

打表找規律
3 2 1
3 5 7
3 7 11
3 8 13
n*m-n-m

python代碼

n,m=map(int,input().split())
print(n*m-n-m)

知識點

找規律

題目5 螞蟻感冒

長 100 厘米的細長直桿子上有 n 只螞蟻。

它們的頭有的朝左，有的朝右。

每只螞蟻都只能沿著桿子向前爬，速度是 1 厘米/秒。

當兩只螞蟻碰面時，它們會同時掉頭往相反的方向爬行。

這些螞蟻中，有 1 只螞蟻感冒了。

并且在和其它螞蟻碰面時，會把感冒傳染給碰到的螞蟻。

請你計算，當所有螞蟻都爬離桿子時，有多少只螞蟻患上了感冒。

輸入格式

第一行輸入一個整數 n, 表示螞蟻的總數。

接著的一行是 n 個用空格分開的整數 Xi, Xi 的絕對值表示螞蟻離開桿子左邊端點的距離。

正值表示頭朝右，負值表示頭朝左，數據中不會出現 0 值，也不會出現兩只螞蟻占用同一位置。

其中，第一個數據代表的螞蟻感冒了。

輸出格式

輸出1個整數，表示最后感冒螞蟻的數目。

數據范圍

1<n<50,
0<|Xi|<100

輸入樣例1：

3
5 -2 8

輸出樣例1：

1

輸入樣例2：

5
-10 8 -20 12 25

輸出樣例2：

3

思路

只考慮什么情況會對結果產生影響？（第一個是感冒的）

• 第一個螞蟻向右運動，位于第一個螞蟻右側，且向左運動
• 第一個螞蟻向左運動，位于第一個螞蟻左側，且向右運動

python代碼

n=int(input())
data=list(map(int,input().split()))left=0
right=0
ans=1#最初的第一個數據是感冒的for i in range(1,n):if data[i]<0 and abs(data[i])>abs(data[0]):right+=1elif data[i]>0 and abs(data[i])<abs(data[0]):left+=1if data[0]>0:#第一個螞蟻是向右的，位于右側且所有向左運動的都會感冒if right>0:ans+=(right+left)else:ans=1
else:if left>0:ans+=(right+left)else:ans=1
print(ans)   

題目6 飲料換購

樂羊羊飲料廠正在舉辦一次促銷優惠活動。樂羊羊C型飲料，憑3個瓶蓋可以再換一瓶C型飲料，并且可以一直循環下去(但不允許暫借或賒賬)。

請你計算一下，如果小明不浪費瓶蓋，盡量地參加活動，那么，對于他初始買入的 n 瓶飲料，最后他一共能喝到多少瓶飲料。

輸入格式

輸入一個整數 n,表示初始買入的飲料數量。

輸出格式

輸出一個整數，表示一共能夠喝到的飲料數量。

數據范圍

0<n<10000

輸入樣例：

100

輸出樣例：

149

python代碼

n=int(input())
gz=n#蓋子初始數量為n
ans=n#最終喝了多少瓶
while gz>=3:bottle,newgz=divmod(gz,3)ans+=bottlegz=bottle+newgz
print(ans)

知識點

1. 沒什么知識點，就是簡單模擬題目