【蓝桥杯python研究生组备赛】005 数学与简单DP

题目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. 没什么知识点，就是简单模拟题目