小蓝xlanll

这个屌丝很懒，什么也没留下！

热门标签

【完整版】蓝桥杯竞赛python算法笔记代码模板｜吐血总结｜蓝桥杯省赛国赛_蓝桥杯算法妮妮的

作者：小蓝xlanll | 2024-05-07 22:33:16

踩

蓝桥杯算法妮妮的

蓝桥杯竞赛python算法笔记代码模板｜吐血总结

文章目录

蓝桥杯竞赛python算法笔记代码模板｜吐血总结

1 二分

1.1 二分求最大满足（check红色条件）

def check(x):
  if(s[x]<=goal): return True
  return False

s=[int(i) for i in input().split()]
goal=int(input())

left=0
right=len(s)-1
while(left<right):
  mid=(left+right+1)>>1
  if(check(mid)):
    left=mid
  else:
    right=mid-1
print(left,s[left])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.2 二分求最小满足（check绿色条件）

def check(x):
  if(s[x]>=goal):
    return True
  return False

s=[int(i) for i in input().split()]
goal=int(input())

left=0
right=len(s)-1
while(left<right):
  mid=(left+right)>>1
  if(check(mid)):
    right=mid
  else:
    left=mid+1
print(left,s[left])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2 双指针算法

2.1 求最长的不包含重复数字的连续子序列

# 只会遍历整个数组一次
j=0
for i in range(n):
  while(j<=i and check(j,i)):
    j-=1
  res=max(res,i-j-1)
1
2
3
4
5
6

3 排列组合

3.1 next_permutation 重排列一个序列生成它的上一个序列

本代码的原题是luogu的火星人

# 对于12345的序列 最多让我数到54321
def nextP(index):
  	global s
    for t in range(index):
        if(n<=1): # 如果一共的字母小于等于1 没什么要干的 返回
            return
        for i in range(n-2,-1,-1): 
          # 从后往前看 找到第一个不是降序的数x
            if(s[i]<s[i+1]): 
                for j in range(n-1,-1,-1): 
                    if(s[j]>s[i]): # 从后往前找 找到第一个大于x的数
                        s[i],s[j]=s[j],s[i] # 把它们交换
                        s[i+1:]=sorted(s[i+1:]) # 后面按照升序排序
                        break 
                break
            else:
                if(i==0): s.sort()
n=int(input())
index=int(input())
s=[int(i) for i in input().split()]

nextP(index)
print(' '.join(map(str,s)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 没有括号的版本
def nextP(index):
	global s
	for t in range(index):
		for i in range(n-2,-1,-1):
			if s[i]<s[i+1]:
				for j in range(n-1,-1,-1):
					if s[j]>s[i]:
						s[i],s[j]=s[j],s[i]
						s[i+1:]=sorted(s[i+1:])
						break
				break
			else:
				if i==0:
					s.sort()
n=int(input())
index=int(input())
s=[int(i) for i in input().split()]

if n>1:
	nextP(index)
print(" ".join(map(str,s)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.2 pre_permutation 重排列一个序列生成它的上一个序列

# 相当于next_permutation的反转做法
def preP(index):
    global s
    for t in range(index):
        if n <= 1: return
        for i in range(n-2,-1,-1):
            if s[i]>s[i+1]: 
                for j in range(n - 1,-1,-1):
                    if s[j]<s[i]:
                        s[j],s[i]=s[i],s[j]
                        s[i+1:]=sorted(s[i+1:],reverse=True)
                        break
                break
            else:
                if i==0:
                    s=sorted(s,reverse = True) # 按照降序排序

n = int(input())
index = int(input())
s = [int(i) for i in input().split()]
preP(index)

print(' '.join(map(str,s)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.3 n个数字/字母的不同排列

# n个数字的不同排列
from itertools import permutations
n=int(input())
s=[i for i in input().split()]
for p in permutations(s):
  print("".join(map(str,p)))

# n个字母的不同排列
str=list(input().split()) # 根据空格划分开
for p in permutations(str):
  print("".join(p))
1
2
3
4
5
6
7
8
9
10
11

3.4 n个数字选k个数的组合

⚠️在组合中有345就不会有435这样的是组合彼此之间没有顺序

from itertools import combinations
n,k=map(int,input().split())
s=[i for i in range(1,n+1)]
for comb in combinations(s,k):
  print("".join(map(str,comb)))
1
2
3
4
5

3.5 n个数字中选1~n个数的不同组合

3.5.1 自己写dfs的方法

# 选择1-n个数的组合都会枚举
n = int(input())
vis = [False for i in range(n)]

def dfs(index):
    if index == n:
        res = []
        for i in range(n):
            if vis[i]:
                res.append((str(i + 1)))
        print(' '.join(res))
        return
    vis[index] = True
    dfs(index + 1)
    vis[index] = False # 复原现场
    dfs(index + 1)

dfs(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.5.2 用combinations产生长度为1~n的组合

from itertools import combinations
n,k=map(int,input().split())
s=[i for i in range(1,n+1)]
ans=[]
for j in range(1,n+1): # 把从n中选1 从n中选2 ... 从n中选n的情况都枚举一次
	for comb in combinations(s,j):
		print("".join(map(str,comb)))
1
2
3
4
5
6
7

4 组合数计算

组合数用这个公式来计算：

$C_a^b=C_{a-1}^b+C_{a-1}^{b-1}$ 表示从a个苹果选择b个苹果可以把选法（不重合不漏）分为2大类

包含此苹果 $C_{a-1}^{b-1}$
不包含此苹果 $C_{a-1}^b$

# 求组合数Cab

N=2010
mod=1e9+7
c=[[0 for i in range(N)] for j in range(N)]

def gen():
  global c
  for i in range(N):
    for j in range(i+1):
      if(j==0): # 
        c[i][j]=1
      else: # 用公式计算c[i][j]
        c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod

n=int(input())
gen()
for k in range(n):
  a,b=map(int,input().split())
  print(c[a][b])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

5 快速幂

利用 $a^{2^0},a^{2^1}...a^{2^{log(k)}}$ 快速计算出幂（二进制的思想）

def qpow(a,k,mod):
    res=1
    while(k):
        if(k&1): # 这里是取最后一位数
            res=res*a%mod
        k>>=1 # 右移一位
        a=a*a%mod # 把乘积翻倍
    return res

n=int(input())
for k in range(n):
    a,k,p=map(int,input().split())
    print(qpow(a,k,p))
1
2
3
4
5
6
7
8
9
10
11
12
13

6 求质数

6.1 试除法

代码略

6.2 朴素筛法

# 朴素筛法
N=1000010
n=int(input())
st=[0 for i in range(N)] # 记录是否是质数 0表示是质数
primes[0 for i in range(N)]
cnt=0

def get_primes(n): # 找出1-n的所有质数并存在primes[]数组中
  global cnt,primes
  for i in range(2,n+1):
    if(st[i]==0): # i是质数
      primes[cnt]=i
      cnt+=1
      for j in range(i+i,n+1,i):
        st[j]=1

get_primes(n)
print(cnt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

6.3 线性筛质数-只用最小质因子来筛

# 线性筛质数
N=1000010
n=int(input())
cnt=0
primes=[]
def get_primes(n):
    global cnt,primes
    st=[False for i in range(N)]
    for i in range(2,n+1):
        if(st[i]==0):
            primes.append(i)
            cnt+=1
        for j in range(N):
            if(primes[j]>n//i): break
            st[primes[j]*i]=1
            if(i%primes[j]==0): break
get_primes(n)
print(cnt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

7 约数和约数有关

7.1 输出所有的约数

def get_divisor(n):
    res=[]
    for i in range(1,x+1):
        if i>x/i: break
        if x%i==0:
            res.append(i)
            if x//i!=i: res.append(x//i)
    res=sorted(res)
    return res

n=int(input())
for k in range(n):
    x=int(input())
    res=get_divisor(x)
    print(" ".join(map(str,res)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

7.2 约数的个数

7.2.1 约数的个数1

def get_divisor(n):
    res=0
    for i in range(1,x+1):
        if i>x/i: break
        if x%i==0:
            res+=1
            if x//i!=i: res+=1
    return res

n=int(input())
for k in range(n):
    x=int(input())
    res=get_divisor(x)
    print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

7.2.2 约数的个数2

def get_divisor(x):
    global primes
 
    for i in range(2,x+1):
        if i*i>x: break
        while x%i==0:
            x=x//i
            if i in primes.keys(): primes[i]+=1
            else: primes[i]=1       
    if x>1: # 最后剩下的部分
        if x in primes.keys(): primes[x]+=1
        else: primes[x]=1

mod=1e9+7
n=int(input())
primes={}
for i in range(n):
    t=int(input())
    get_divisor(t)
res=1
for p in primes.values():
    res=res*(p+1)%mod
print(round(res))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

7.3 质因子分解

n的因数个数=n分解质因数后每个质因子的指数+1再相乘

def get_divisor(x):
    primes={}
    
    for i in range(2,round(x/i)+2):
        if i*i>x: break
        while x%i==0:
            x=x//i
            primes[i]+=1
    if x>1 primes[x]+=1
    
    res=1
    for p in primes:
        print(p)   
1
2
3
4
5
6
7
8
9
10
11
12
13

8 欧几里得算法

8.1 欧几里得

# 简单的最大公约数
def gcd(a,b):
    if b==0: return a
    return gcd(b,a%b)
1
2
3
4

8.2 最小公倍数

最小公倍数=两整数的乘积/最大公约数

# 最小公倍数需要调用最大公约数函数
def gbs(a,b):
    return a*b//(gcd(a,b))

def gcd(a,b):
    if b==0: return a
    return gcd(b,a%b)
1
2
3
4
5
6
7

9 图和树有关

9.1 建图方法

# 建立邻接表
N=100010
e=[0 for i in range(N)] # 存放的是各边的到达结点的号
ne=[0 for i in range(N)] # next指针数组 存放的邻接表的下一个节点的位置
h=[-1 for i in range(N)] # 头指针数组 指向这个结点的相邻结点(存放头结点在e中的index)
w=[0 for i in range(N)] # 边的权值
# dis数组存的是到达对应index结点的最短距离
idx=0

def add(a,b,c):
  global idx,e,ne,h,w
  e[idx]=b
  w[idx]=c
  ne[idx]=h[a]
  h[a]=idx
  idx+=1

# 访问某一个点的邻边的时候
t=h[a]
while(t!=-1):
  node=e[t] # 一定要去e[t]才是真的点 不然只是一个下标
  # 对这个node进行一波操作
  t=ne[t]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

9.2 最短路算法

9.2.1 单源最短路-dijkstra

dijkstra算法必须规定起点

（1）朴素dijkstra

不常用背诵下面优化的dijkstra比较好

# 朴素 使用邻接矩阵存
N=510
g=[[float('inf') for i in range(N)] for j in range(N)]
st=[False for i in range(N)]
dist=[float('inf') for i in range(N)]

def dijkstra(start,end): # 从点start走到点end的路径
  global dist,st,g
  dist[start]=0
  for i in range(n): # 遍历从start开始的n个点
    t=-1
    for j in range(1,n+1):
      if(st[j]==False and (t==-1 or dist[t]>dist[j])): # t==-1 表示是遇到的第一个点 dist[t]>dist[j]表示要更新当前路径最短的点
        t=j
      if(t==end): # 最短路已经更新到了end
        break # 如果要寻找到所有点的最短路不知道还要不要break
      st[t]=True
      
      for j in range(1,n+1):
        dist[j]=min(dist[j],dist[t]+g[t][j])
      
    if(dist[end]==float('inf')): return -1
    return dist[end]
      
n,m=map(int,input().split())
for k in range(m):
  a,b,c=map(int,input().split())
  g[a][b]=min(g[a][b],c)
print(dijkstra(1,n))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

（2）堆优化dijkstra

import heapq
# 加入堆的操作 heapq.heappush(queue,(dis,node))
# 拿出堆的操作 heapq.heappop(queue)

def add(a,b,c):
    global w,e,ne,h,idx
    w[idx]=c
    e[idx]=b
    ne[idx]=h[a]
    h[a]=idx
    idx+=1

def dijskta(s):
    queue=[]
    dis=[float('inf') for i in range(n+10)]
    dis[s]=0 # 注意初始化出发点的dis为0
    heapq.heappush(queue,(0,s)) # 注意把初始结点和距离0加入堆
    while(queue):
        t=heapq.heappop(queue)
        curDis=t[0]
        curNode=t[1]
        i=h[curNode] # 表示遍历从i出发的边
        while(i!=-1):
            if(dis[e[i]]>curDis+w[i]):
                dis[e[i]]=curDis+w[i]
                heapq.heappush(queue,(dis[e[i]],e[i])) # 注意dis都是根据点来的
            i=ne[i]
    return dis

    
N=100010
n,m=map(int,input().split())
e=[0 for i in range(N)]
ne=[0 for i in range(N)]
w=[0 for i in range(N)]
h=[-1 for i in range(N)] # 千万注意h头指针数组要初始化为-1
idx=0

for i in range(m):
    a,b,c=map(int,input().split())
    add(a,b,c)
dis=dijskta(1)

if(dis[n]==float('inf')):
    print(-1)
else:
    print(dis[n])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

9.2.2 多源汇最短路-SPFA算法

SPFA是bellman-ford的改进版

SPFA算法可以算出从起点到任何点的最短路

# SPFA 非常通用的一个算法！
def add(a,b,c):
    global idx,e,ne,w,h
    e[idx]=b
    ne[idx]=h[a]
    w[idx]=c
    h[a]=idx
    idx+=1
    
def SPFA():
    queue=[]
    st=[False for i in range(n+10)] # st表示当前这个点在不在队列当中，防止存储重复的点
    dist=[float('inf') for i in range(n+10)]
    queue.append(1)
    dist[1]=0
    st[1]=True 

    while(queue):
        t=queue.pop(0)
        st[t]=False
        i=h[t]
        while(i!=-1):
            node=e[i]
            # print(node)
            if(dist[node]>dist[t]+w[i]):
                dist[node]=dist[t]+w[i]
                if(st[node]==False):
                    queue.append(node)
                    st[node]=True
            i=ne[i]

    if(dist[n]==float('inf')): return -1
    return dist[n]

n,m=map(int,input().split())
e=[0 for i in range(100010)]
ne=[0 for i in range(100010)]
h=[-1 for i in range(n+10)]
w=[0 for i in range(100010)]
idx=0

for i in range(m):
    a,b,c=map(int,input().split())
    add(a,b,c)
    
t=SPFA()
if(t==-1): print("impossible")
else: print(t)  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

9.3 最小生成树算法

最小生成树算法在无向图上使用，背下来kruskal就可以了

9.3.1 kruskal最小生成树

每次选取边的权值最小的边加入边集，如果形成了环就撤销这条边，如果不形成边就继续。直到所有点都被连接。

# kruskal
def find(x):
    if(x!=p[x]):
        p[x]=find(p[x])
    return p[x]

n,m=map(int,input().split())
edges=[]

for i in range(m):
    a,b,c=map(int,input().split())
    edges.append([a,b,c])
edges=sorted(edges,key=lambda x:x[2])

res=0
cnt=0
p=[i for i in range(n+1)]

for i in range(m):
    a=edges[i][0]
    b=edges[i][1]
    w=edges[i][2]
    a=find(a),b=find(b)
    if(a!=b):
        res+=w
        cnt+=1
        p[a]=b
if(cnt<n-1):
    print("impossible")
else:
    print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

9.3.2 prim最小生成树

不常用一般用kruskal

N=510
INF=float('inf')
dis=[float('inf') for i in range(N)]
def prim():
    global dis
    res=0
    
    for i in range(n):
        t=-1
        for j in range(1,n+1):
            if st[j]==False and (t==-1 or dis[t]>dis[j]):
                t=j
        if i and dis[t]==: return INF
        if i: res+=dis[t]
        st[i]=1
        for j in range(1,n+1):
            dis[j]=min(dis[j],g[t][j])
    
    return res
        
n,m=map(int,input().split())

g=[[INF for i in range(N)] for j in range(N)]
st=[0 for i in range(N)]
for i in range(1,n+1):
    for j in range(1,n+1):
        if i==j:
            g[i][j]=0
        
for i in range(m):
    a,b,c=map(int,input().split())
    temp=min(g[a][b],c)
    g[a][b],g[b][a]=temp,temp
    
t=prim()
if t==INF: print("impossible")
else: print(t)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

9.3.3 拓扑排序

# topsort()
def add(a,b):
    global ind,e,ne,h,idx
    e[idx]=b
    ind[b]+=1
    ne[idx]=h[a]
    h[a]=idx
    idx+=1

def topsort():
    queue=[]
    ans=[]
    for i in range(1,n+1):
        if(ind[i]==0):
            queue.append(i)
    while(queue):
        t=queue.pop(0)
        ans.append(t)
        i=h[t]
        while(i!=-1):
            ind[e[i]]-=1
            if(ind[e[i]]==0):
                queue.append(e[i])
            i=ne[i]
    return ans

N=100010
n,m=map(int,input().split()) 
h=[-1 for i in range(n+10)]
e=[0 for i in range(m+10)]
ne=[0 for i in range(m+10)]
ind=[0 for i in range(n+10)]
idx=0

for i in range(m):
    a,b=map(int,input().split())
    add(a,b)

ans=topsort()
if(len(ans)<n): # 如果拓扑排序中序列点的个数小于n 表示没有形成拓扑排序
    print(-1)
else:
    print(" ".join(map(str,ans)))
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

10 差分算法

10.1 一维差分-地毯为例

n,m=map(int,input().split())
f=[[0 for i in range(n+10)] for j in range(n+10)]

for i in range(m):
    x1,y1,x2,y2=map(int,input().split())
    for j in range(x1,x2+1):
        f[j][y1]+=1
        f[j][y2+1]-=1

for i in range(n+1):
    for j in range(1,n+2):
        f[i][j]+=f[i][j-1]
        
for i in range(1,n+1):
	for j in range(1,n+1):
		print(f[i][j],end=' ')
	print("")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

10.2 二维差分-luogu的激光炸弹

思路与一维差分类似

11 并查集

# 并查集find函数
def find(x):  
    if(x!=p[x]):  p[x]=find(p[x])  
    return p[x]
# 并查集union函数
for i in range(m):  
    a,b=map(int,input().split())  
    pa,pb=find(a),find(b)  
    if(pa!=pb): p[pa]=pb # 注意这里的操作！！
1
2
3
4
5
6
7
8
9

12 DFS和BFS

12.1 DFS

内部搜索（棋盘的结点作为结点）
外部搜索（棋盘的状态作为结点）

# dfs基本框架
def dfs():
    
1
2
3

12.2 BFS-和最短路有关的问题

# bfs基本框架
queue=[]
queue.append([sx,sy]) # 初始结点入队
while(queue):  
    front=queue.pop(0)  
    ...
1
2
3
4
5
6

bfs最经典的是最短步数问题，每次向各个方向走一步的时候就step+1

13 DP背包模版（重点）

13.1 01背包

（1）二维/基本的01背包

# 01背包基本模版
N=1010
n,m=map(int,input().split())
v=[0 for i in range(N)]
w=[0 for i in range(N)]
f=[[0 for i in range(N)] for j in range(N)]
for i in range(1,n+1):
  vv,ww=map(int,input().split())
  v[i]=vv
  w[i]=ww
  
for i in range(1,n+1):
  for j in range(m+1):
    f[i][j]=f[i-1][j]
    if(j>=v[i]):
      f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i])
print(f[n][m])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（2）一维的01背包

# 01背包 一维模版
N=1010
w=[0 for i in range(N)]
v=[0 for i in range(N)]
f=[0 for j in range(N)]
n,m=map(int,input().split())

for i in range(1,n+1):
    v[i],w[i]=map(int,input().split())

for i in range(1,n+1):
    for j in range(m,-1,-1):
        if(j>=v[i]):
            f[j]=max(f[j],f[j-v[i]]+w[i])
print(f[m])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

13.2 完全背包

（1）朴素完全背包

# 朴素的完全背包
N=1010
v=[0 for i in range(N)]
w=[0 for i in range(N)]
f=[[0 for i in range(N)] for j in range(N)]

n,m=map(int,input().split())
for i in range(1,n+1):
  v[i],w[i]=map(int,input().split())

for i in range(1,n+1):
  for j in range(m):
    for k in range(j//v[i]+2):
      if(k*v[i]>j):
        break
      f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k)
      
print(f[n][m])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（2）优化的二维完全背包

# 优化的二维完全背包
N=1010
v=[0 for i in range(N)]
w=[0 for i in range(N)]
f=[[0 for i in range(N)] for j in range(N)]

n,m=map(int,input().split())
for i in range(1,n+1):
  v[i],w[i]=map(int,input().split())

for i in range(1,n+1):
  for j in range(m+1): # 注意这里+1
    f[i][j]=f[i-1][j]
    if(j>=v[i]):
      f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]) # 注意这里是f[i][j-v[i]]+w[i] 对比01背包的f[i-1][j-v[i]]+w[i]
      
print(f[n][m])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（3）优化的一维完全背包

# 优化的一维完全背包
N=1010
v=[0 for i in range(N)]
w=[0 for i in range(N)]
f=[0 for i in range(N)]

n,m=map(int,input().split())
for i in range(1,n+1):
  v[i],w[i]=map(int,input().split())

for i in range(1,n+1):
  for j in range(v[i],m+1): # 一维完全背包是从v[i]~m正向
    f[j]=max(f[j],f[j-v[i]]+w[i])
    
print(f[m])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

13.3 多重背包

（1）朴素的多重背包

# 朴素多重背包（完全背包+一个小小的限制条件）
N=1010
w=[0 for i in range(N)]
v=[0 for i in range(N)]
f=[[0 for i in range(N)] for j in range(N)]
s=[0 for i in range(N)]

for i in range(1,n+1):
    v[i],w[i],s[i]=map(int,input().split())

for i in range(1,n+1):
    for j in range(m+1):
        for k in range(s[i]+1):
            if(k*v[i]>j):
                break
            f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k)
print(f[n][m])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

摆花典型的多重背包求方案数

# 摆花 典型的多重背包求方案数
mod=1000007
n,m=map(int,input().split())
f=[0 for i in range(110)]
s=[int(i) for i in input().split()]
f[0]=1

for i in range(n): # 枚举花的种类
  for j in range(m,-1,-1): # 枚举背包容量
    for k in range(1,min(s[i],j)+1): # 既不能大于花最大数s[i] 也不能大于当前背包容量j
      f[j]=(f[j]+f[j-k])%mod
      
print(f[m])
1
2
3
4
5
6
7
8
9
10
11
12
13

（2）二进制优化的多重背包

# 二进制优化的多重背包
# 分组为1,2....2^k,r的背包
# 然后作为01背包
N=1010
v=[0 for i in range(N)]
w=[0 for i in range(N)]
f=[0 for j in range(N)]
s=0
cnt=0
n,m=map(int,input().split())
for i in range(1,n+1):
  a,b,s=map(int,input().split())
  k=1
  # 分组
  while(k<=s):
    cnt+=1
    v[cnt]=a*k
    w[cnt]=b*k
    s-=k
    k*=2
  if(s>0):
    cnt+=1
    v[cnt]=s*a
    w[cnt]=s*b
   
n=cnt
for i in range(1,n+1):
  for j in range(m,v[i]-1,-1):
    f[j]=max(f[j],f[j-v[i]]+w[i])
    
print(f[m])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

13.4 分组背包-类似多重背包

# 一维的分组背包
N=2010
n,m=map(int,input().split())
s=[0 for i in range(N)]
v=[[0 for i in range(N)] for j in range(N)]
w=[[0 for i in range(N)] for j in range(N)]
f=[0 for i in range(N)]

for i in range(1,n+1):
    s[i]=int(input())
    for j in range(s[i]): # 第i组有s[i]个物品
        v[i][j],w[i][j]=map(int,input().split()) # i组中的物品体积和价值


for i in range(1,n+1):
    for j in range(m,-1,-1):
        for k in range(s[i]):
            if(j>=v[i][k]):
                f[j]=max(f[j],f[j-v[i][k]]+w[i][k])
print(f[m])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

14 DP数字三角形

从下到上更新

n=int(input())
f=[]
for i in range(n):
    f.append([int(i) for i in input().split()])

for i in range(n-2,-1,-1): # 从n-2(倒数第二行)到0行
  for j in range(i+1): # 列内按从左到右 一列的数字个数是i+1个
    f[i][j]+=max(f[i+1][j],f[i+1][j+1]) # 左下和右下较大
print(f[0][0])
1
2
3
4
5
6
7
8
9

从上到下更新

n=int(input())
f=[]
for i in range(n):
    f.append([int(i) for i in input().split()])

for i in range(1,n): # 从正数第一行(0行)到n-1行
  for j in range(i+1):
    if(j==0): # 如果是第一列 只会从f[i-1][j]转移过来
      f[i][j]+=f[i-1][j]
    elif(j==i): # 如果是最后一列 只会从f[i-1][j-1]转移过来
      f[i][j]+=f[i-1][j-1]
    else: # 如果是中间列 需要判断从哪里转移
      f[i][j]+=max(f[i-1][j],f[i-1][j-1])

res=-10010
for i in range(n):
  res=max(res,f[n-1][i])
print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

15 DP的LCS模版

最长上升子序列

n=int(input())
a=[int(i) for i in input().split()]
f=[1 for i in range(n+10)]
res=1

for i in range(n):
	for j in range(i):
		if a[i]>a[j]:
			f[i]=max(f[i],f[j]+1)
	res=max(f[i],res)
print(res)
1
2
3
4
5
6
7
8
9
10
11

最长公共子序列

# 两个序列长度相同
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
f=[[0 for i in range(n+10)] for j in range(n+10)]

for i in range(n):
	for j in range(n):
		if(i>0 and j>0):
			f[i][j]=max(f[i-1][j],f[i][j-1])
		elif(i>0):
			f[i][j]=f[i-1][j]
		elif(j>0):
			f[i][j]=f[i][j-1]
		if(a[i]==b[j]):
			f[i][j]=max(f[i][j],f[i-1][j-1]+1)
res=0
for i in range(n):
	res=max(res,f[i][n-1])
print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 最长公共子序列通用版
a=list(input())
b=list(input())
len1=len(a)
len2=len(b)
f=[[0 for i in range(max(len1,len2)+10)] for j in range(max(len1,len2)+10)]

for i in range(len1):
  for j in range(len2):
    if(i>0 and j>0):
			f[i][j]=max(f[i-1][j],f[i][j-1])
		elif(i>0):
			f[i][j]=f[i-1][j]
		elif(j>0):
			f[i][j]=f[i][j-1]
		if(a[i]==b[j]):
			f[i][j]=max(f[i][j],f[i-1][j-1]+1)
res=0
for i in range(n):
  res=max(res,f[i][len2-1])
print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

最长公共上升子序列

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=3010;
int n;
int a[N],b[N];
int f[N][N];

int main()
{
  cin>>n;
  for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
  for(int i=1;i<=n;i++)
    scanf("%d",&b[i]);
  
  for(int i=1;i<=n;i++)
  {
    int maxv=1;
    for(int j=1;j<=n;j++)
    {
      f[i][j]=f[i-1][j];
      if(a[i]==b[j]) f[i][j]=max(f[i][j],maxv);
      if(b[j]<a[i]) maxv=max(maxv,f[i][j]+1);
    }
  }
  int res=0;
  for(int i=1;i<=n;i++)
    res=max(res,f[n][i]);
  cout<<res;
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

16 记忆化搜索

摘花生

# 摘花生dp做法
T=int(input())
for t in range(T):
  n,m=map(int,input().split())
  f=[[] for j in range(110)]
  f[0]=[0 for i in range(m+1)]
  for i in range(1,n+1):
    f[i]=[0]+[int(i) for i in input().split()]
  for i in range(1,n+1):
    for j in range(1,m+1):
      f[i][j]+=max(f[i-1][j],f[i][j-1])
  print(f[n][m])
1
2
3
4
5
6
7
8
9
10
11
12

# 摘花生记忆化搜索
def dfs(x,y):
  global res,cur
  dx=[1,0]
  dy=[0,1]
  cur+=f[x][y]
  if(x==n and y==m):
    res=max(res,cur)
    return
  for i in range(2):
    xx=x+dx[i]
    yy=y+dy[i]
    if(xx<1 or yy<1 or xx>=n or yy>=m): continue
    dfs(xx,yy)
  cur-=f[x][y]

T=int(input())
res=0
cur=0
for t in range(T):
  n,m=map(int,input().split())
  f=[[] for j in range(110)]
  f[0]=[0 for i in range(m+1)]
  for i in range(1,n+1):
    f[i]=[0]+[int(i) for i in input().split()]
dfs()  
print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

901滑雪

dp分析

集合表示所有从i,j开始滑的路径属性是Max
状态计算

# 记忆化搜索
n,m=map(int,input().split())
N=310
dx=[1,-1,0,0]
dy=[0,0,1,-1]
f=[[-1 for i in range(N)] for j in range(N)]
h=[]

for i in range(1,n+1):
    h.append([int(j) for j in input().split()])

def dp(x,y):
    global f
    if(f[x][y]!=-1): return f[x][y]
    f[x][y]=1
    for i in range(4): # 四个方向遍历
        a,b=x+dx[i],y+dy[i]
        if(a<0 or a>=n or b<0 or b>=m): continue
        if(h[a][b]>=h[x][y]): continue
        f[x][y]=max(f[x][y],dp(a,b)+1)
    return f[x][y]

res=0
for i in range(n):
    for j in range(m):
        res=max(res,dp(i,j))
print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/551630

【完整版】蓝桥杯竞赛python算法笔记 代码模板｜吐血总结｜蓝桥杯省赛国赛_蓝桥杯算法妮妮的

蓝桥杯竞赛python算法笔记 代码模板｜吐血总结