头像

大佬复制品




离线:17小时前


最近来访(5)
用户头像
kyle_z
用户头像
爱编程的胖子
用户头像
smcsurvey
用户头像
党梦竹
用户头像
Code-Z


方格取数(python)

思路

最关键的是分为两类,一类是从上往下和从从左向右取最大值,一类是从下往上和从左往右取最大值,所以每个f[i][j]有两次更新,一次是从下往上,一次是从上往下

python 代码 $O(nm)$


#状态表示:从f[1][1]到f[i][j]向上、向下或向右且下一步向右的所有集合(这里向右是因为,一个位置只有四种放向,列举了上下左三个方向,就只剩向右一个方向了)

#状态计算:s=max(s,f[i][j-1])+shu[i-1][j-1],f[i][j]=max(f[i][j],s)

#这里有个小细节得注意,初始化一定要赋值为无穷大,有个测试点的开头一列为负数,如果赋值为0就会把开头的这一列负数给自动忽略

n,m=map(int,input().split())

shu=[]

for i in range(n):
    shu.append([int(i) for i in input().split()])
f=[[float('-inf') for i in range(m+1)] for j in range(n+1)]
f[1][0]=0
for j in range(1,m+1):
    s=float('-inf')
    for i in range(1,n+1):
        #找到上一个节点的最大值,然后再加上该节点即是这个节点的最大值(新算出的值)
        s=max(s,f[i][j-1])+shu[i-1][j-1]
        #更新f[i][j],这里会有从上往下,和从下往上两个方向,因此这里要设置一个f[i][j]和新算出的值做一个更新
        f[i][j]=max(s,f[i][j])
    s=float('-inf')
    for i in range(n,0,-1):
        s=max(s,f[i][j-1])+shu[i-1][j-1]
        f[i][j]=max(s,f[i][j])
print(f[n][m])



题目描述

思路:

y总说过了,考虑不重不漏原则,以i为结尾,前面的元素都可能是倒数第二个元素,把全面所有可能是倒数第二个元素考虑进去

494b9c5310d62b39e1526e8379bccc1.png

这里代码的关键是理解,i,j双重循环,第一重求的以i结尾的,第二重求所有以i结尾的有严格上升子序列的所有集合的最大值,知道f[i]是怎样更新的,f[j]里面存的什么值


python 代码 $O(n^2)$

#状态表示:所有以i结尾的严格单调上升的子序列所有集合
#状态计算:f[i]=f[j]+1和f[i]的一个最大值


N=int(input())

shu=[]

shu=list(map(int,input().split()))

f=[0 for i in range(N+1)]

#以i为结尾的所有严格单调递增子序列的集合的最大值
for i in range(N):
    f[i]=1
    #j遍历的是i前面有那些数严格小于a[i],并用j不断更新i,以便取得最大值
    #比如1,7,3,5,9  9大于1,就在前面存储1的地方f[0]+1,9大于7,就在前面存储7的地方f[1]+1
    #9大于3,就在前面存储1的地方f[2]+1,9大于5,就在前面存储5的地方f[3]+1,最后f[i]就是这几个数的最大值
    for j in range(i):
        if(shu[j]<shu[i]):
            f[i]=max(f[i],f[j]+1)
res=0
#每次求的是以i结尾的最长子序列的长度,不是全部序列的,因此全部序列需要遍历每个节点的最长子序列的值,求最大
for i in range(N):
    res=max(res,f[i])

print(res)



摘花生(python)

思路

dp算法最关键的是空间换时间,即把每一次计算存储在一个空间中,每次需要的时候找到该位置直接调用,不需要再次计算。

  • 动态规划问题要注意两个点:1、不重 2、不漏

  • 不重的话,不是必要条件,对于属性为min、max的题目可以忽略,对于属性为count的题目不可以忽略

  • 不漏的话,这是必要条件

状态表示:
集合:从…到f[i][j]的所有集合(一般是考虑限制条件那句话,假设第f[i][j]存的是最后一个元素,那么选择或则到达该元素有哪些集合,遵守不重不漏)
属性:题目求的

状态计算:
假如i,j为最后一个点,有几种方案,


C++ 代码 $O(n^2)$

#状态表示:
# 集合:从f[1][1]到f[i][j]的所有集合
# 属性:最大值

#状态计算:
# 假如i,j为最后一个点,有几种方案,
# f[i][j]=f[i-1][j]+f[i][j-1]

T=int(input())
for i in range(T):
    hang=[]
    R,C=map(int,input().split())
    for i in range(R):
        hang.append([int(i) for i in input().split()])

    f=[[0 for m in range(C+1)] for n in range(R+1)]

    for n in range(1,R+1):
        for m in range(1,C+1):
            f[n][m]=max(f[n-1][m],f[n][m-1])+hang[n-1][m-1]

    print(f[R][C])




完全背包问题(python)

思路

01背包和完全背包最大的不同在于01背包只考虑一个物品选还是不选只有两种情况,完全背包需要考虑一个物品需要选几次,1,2,3,4,5,6.....然后再,把得到的等式做一个优化,把j换成v-j可以发现,j的等式后面一串等于v-j后面一串再加一个w

4ba6e37438e806fc807a4e57c521143.png

0d7bcb54c2cf7029e93aab4a6f87c5e.png

python 代码 $O(n^2)$

n,v=map(int,input().split())

sum=[]

for i in range(n):#存几个数
    sum.append([int(j) for j in input().split()])#把每一个数都强制转换成int类型,并从0开始存

f=[[0 for i in range(v+1)] for j in range(n+1)]



for i in range(1,n+1):
    for j in range(1,v+1):
        f[i][j]=f[i-1][j]
        if(j>=sum[i-1][0]):#sum里面的i需要减一是因为,i从1开始,而sum里面的i从0开始,不减一,数组下标会越界
            f[i][j]=max(f[i][j],f[i][j-sum[i-1][0]]+sum[i-1][1])

print(f[n][v])




朴素算法

思路

每次例举第i个物品在体积为j的限制下选或者不选,保存能够达到的最大的组合,不选即是除掉第i个物品在相同体积下的最大值,选,即是除掉第i个物品和第i个物品的体积在相同体积下i-1个物品价值,最后求一个最大值。


时间复杂度$O(n^2)$

pyhon 代码

n,v=map(int,input().split())

sum=[]

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


# 初始化,先全部赋值为0,这样至少体积为0或者不选任何物品的时候是满足要求   
f=[[0 for i in range(v+1)] for j in range(n+1)]

#每次例举第i个物品在体积为j的限制下选或者不选,保存能够达到的最大的组合
for i in range(1,n+1):
    for j in range(1,v+1):
        f[i][j]=f[i-1][j]
        if(j>=sum[i-1][0]):# 判断背包容量是不是大于第i件物品的体积
             # 在选和不选的情况中选出最大值
             #1到i中选总体积小于等于j,1到i-1中选总体积小于等于j-vi,
             #这里的i-1是因为sum从0开始存的,这里的i是从1开始存的,因此i要减去1才能和sum里面的数对应
            f[i][j]=max(f[i][j],f[i-1][j-sum[i-1][0]]+sum[i-1][1])


print(f[n][v])




dp优化,都是对代码做等价变形,只能在空间上优化




题目描述

解题思路

从1到n开始遍历,按照题目要求遇到n为偶数,除以二遇到n为基数,3倍加1

时间复杂度(o(n**2)

python 代码

m=int(input())
max=1

for n in range(1,m+1):
    while(n!=1):
        if(n>max):
            max=n
        if(n%2==0):
            n=n//2
        else:
            n=n*3+1
        if(n>max):
            max=n

print(max)



题目描述

python 代码

#递归爆栈,拓扑排序AC
n = int(input())
w = [0]+list(map(int,input().split()))
deg={}
fa={i:[] for i in range(1,n+1)}
f = [i for i in w]
nxt = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    deg[a]=deg.get(a,0)+1
    deg[b]=deg.get(b,0)+1
    fa[b].append(a)
    fa[a].append(b)
queue=[]
for i in deg:
    if deg[i]==1:
        queue.append((i))
visit=set()
while queue:
    u=queue.pop()
    visit.add(u)
    for nxt in fa[u]:
        if nxt not in visit:
            deg[nxt]-=1
            f[nxt]+= max(0,f[u])
            if deg[nxt]==1:
                queue.append((nxt))
res = f[1]
for i in range(2,n+1):
    res = max(f[i],res)
print(res)




密文搜索(python)有错

解题思路

从根号s到long10为底遍历,从后往前,开始循环遍历,直到找出初始数字

C++ 代码

import math
n,s=map(int,input().split(' '))
for i in range(int(math.sqrt(s)),int(math.log10(s)),-1):#缩小范围遍历,从根号s到long10为底遍历,从后往前遍历
    temp=i
    sum=i
    m=i
    for j in range(n):
        temp=2*temp-1
        sum+=temp
        if(sum==s):
            print(m)

这个点过不了
97 2218388550399401452619230609499




题目描述

python 代码

from collections import Counter

string = input().strip()
n, cnt = int(input().split()), 0
password = [input() for _ in range(n)]
for i in password:
    temp = dict(Counter(i))
    for j in range(len(string) - 8 + 1):
        cut = dict(Counter(string[j:j + 8]))
        cnt += 1 if cut == temp else 0
print(cnt)




题目描述

解题思路

这道题与迷宫思路是一样的,运用广度优先的策略,从A点开始遍历,依次遍历该点上下左右,判断该点是否过界,是否已经走过,是否满足题目要求

python 代码

n=int(input())
matrix=[]

for _ in range(n): # 输入数组
    temp=list(map(str,input().split()))
    matrix.append(temp)
path=[[False]*n for _ in range(n)] # 记录该点是否已经走过

def search(x,y,res):
    save=[]
    save.append((x,y,res))#存初始点
    path[x][y]=True

    while save:
        front=save.pop(0)
        x,y,res=front

        if matrix[x][y]=='B':# 遍历到B结束
            return res

        for dx ,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
            nx,ny=dy+x,dx+y
            # 判断,上下,左右移动是否超出边界,该点是否走过,该节点与上一个节点是否相同
            if -1 < ny < n and -1 < nx < n and not path[nx][ny] and matrix[x][y] != matrix[nx][ny]:
                # 该节点设置为走过
                path[nx][ny]=True
                save.append((nx,ny,res+1))
    return -1


for i in range(n):
    for j in range(n):
        if matrix[i][j]=='A':
            print(search(i,j,0))