備戰(zhàn)2024年藍橋杯&算法學習 -- 每日一題
Python大學A組

????????試題一：摘花生
????????試題二：最低通行費用
????????試題三：方格取數
????????試題四：傳紙條

試題一：摘花生

【題目描述】

????????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

【解題思路】

? ? ? ? 線性DP中的數字三角形模型，基礎模型，狀態(tài)轉移方程f[i][j] = max(f[i-1][j] , f[i][j-1]) + w[i][j]。

【Python程序代碼】文章來源地址http://www.zghlxwxcb.cn/news/detail-850747.html

T = int(input())
for _ in range(T):
    r,c = map(int,input().split())
    a = [[0]*(c+5)]
    for i in range(r):
        a.append([0]+list(map(int,input().split())))
    f = [[0]*(c+5) for _ in range(r+5)]
    for i in range(1,r+1):
        for j in range(1,c+1):
            f[i][j] = max(f[i-1][j],f[i][j-1])+a[i][j]
    print(f[r][c])

試題二：最低通行費用

【題目描述】

????????本題大意上給定一個 n×n的矩陣，讓我們從左上角出發(fā)，最終走到右下角走過的方塊數量的不能超過 2n?1個求所有路線中，經過的方塊的總價值最少的路線。

【解題思路】

? ? ? ? 和上一題相比改了一些條件，比如增加了一個不能超過2n-1個方塊，考慮一下（1，1）到（n，n）的曼哈頓距離發(fā)現d = 2*n-2，同時題目要求的是求總價值最小，在2*n-2的最短路徑上加上一個方塊一定會大于等于這2*n-2個方塊的價值，所以本題可以套上面題目的板子。

【Python程序代碼】

n = int(input())
f = [[1e9]*(n+5) for _ in range(n+5)]
a = [[0]*(n+5)]
for i in range(n):
    a.append([0]+list(map(int,input().split())))
f[0][1]=f[1][0]=0
for i in range(1,n+1):
    for j in range(1,n+1):
        f[i][j] = min(f[i][j-1],f[i-1][j])+a[i][j]
print(f[n][n])

試題三：方格取數

【題目描述】

????????設有N×N?的方格圖(N≤9)，我們將其中的某些方格中填入正整數，而其他的方格中則放入數字?0。如下圖所示（見樣例）:

?????????某人從圖的左上角的?A?點出發(fā)，可以向下行走，也可以向右走，直到到達右下角的?B?點。在走過的路上，他可以取走方格中的數（取走后的方格中將變?yōu)閿底?0）。
????????此人從?A?點到?B?點共走兩次，試找出?2?條這樣的路徑，使得取得的數之和為最大。

【輸入數據】

????????輸入的第一行為一個整數?N（表示 N×N?的方格圖），接下來的每行有三個整數，前兩個表示位置，第三個數為該位置上所放的數。一行單獨的?0?表示輸入結束。

【輸出數據】

????????只需輸出一個整數，表示?2?條路徑上取得的最大的和。

【輸入樣例】

8
2 3 13
2 6  6
3 5  7
4 4 14
5 2 21
5 6  4
6 3 15
7 2 14
0 0  0

【輸出樣例】

67

【解題思路】

? ? ? ? 需要考慮兩條路徑，如何考慮更好呢？如果說分別考慮的話如何判斷是否重合呢且這兩者相加也不一定是最大值，所以如果能夠同時考慮兩條路就好了，首先兩條路的曼哈頓距離一定是相等的，所以我們可以考慮枚舉每一條路徑走的行的數量，列的數量可以用曼哈頓距離-列的數量，所以f[k][i][j]表示曼哈頓距離為k，且第一條路徑走了i行k-i列，第二條路徑走了j行k-j列，那么如何考慮狀態(tài)轉移呢？每一個f[k][i][j]可以由第一條路徑往右走或者往下走過來，也即使f[k-1][i][j]和f[k-1][i-1][j]，第二條路徑也是往右或往下，f[k-1][i][j]，f[k-1][i][j-1]，那也就是四種狀態(tài)：f[k-1][i-1][j-1]、f[k-1][i][j-1]、f[k-1][i-1][j]、f[k-1][i][j]。

【Python程序代碼】

n = int(input())
w = [[0]*(n+5) for _ in range(n+5)]
a,b,c = map(int,input().split())
while not (a==0 and b==0 and c==0):
    w[a][b] += c
    a, b, c = map(int, input().split())
f = [[[0]*(n+5) for _ in range(n+5)] for i in range(2*n+5)]
for k in range(2,2*n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if k-i<=0 or k-j<=0 or k-i>n or k-j>n:continue
            v = w[i][k-i]
            t = f[k][i][j]
            if i!=j:v+=w[j][k-j]
            t = max(t, f[k-1][i-1][j-1])
            t = max(t, f[k-1][i][j-1])
            t = max(t, f[k-1][i-1][j])
            t = max(t, f[k-1][i][j])
            f[k][i][j] = t+v
print(f[2*n][n][n])

試題四：傳紙條

【題目描述】

????????小淵和小軒是好朋友也是同班同學，他們在一起總有談不完的話題。一次素質拓展活動中，班上同學安排坐成一個?m 行?n 列的矩陣，而小淵和小軒被安排在矩陣對角線的兩端，因此，他們就無法直接交談了。幸運的是，他們可以通過傳紙條來進行交流。紙條要經由許多同學傳到對方手里，小淵坐在矩陣的左上角，坐標?(1,1)，小軒坐在矩陣的右下角，坐標?(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。?在活動進行中，小淵希望給小軒傳遞一張紙條，同時希望小軒給他回復。班里每個同學都可以幫他們傳遞，但只會幫他們一次，也就是說如果此人在小淵遞給小軒紙條的時候幫忙，那么在小軒遞給小淵的時候就不會再幫忙，反之亦然。?還有一件事情需要注意，全班每個同學愿意幫忙的好感度有高有低（注意：小淵和小軒的好心程度沒有定義，輸入時用?0?表示），可以用一個?0～100的自然數來表示，數越大表示越好心。小淵和小軒希望盡可能找好心程度高的同學來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學的好心程度之和最大?，F在，請你幫助小淵和小軒找到這樣的兩條路徑。

【輸入格式】

????????第一行有?2?個用空格隔開的整數?m?和?n，表示學生矩陣有?m?行?n?列。

????????接下來的?m?行是一個?m×n 的矩陣，矩陣中第?i 行?j 列的整數表示坐在第?i 行?j 列的學生的好心程度，每行的?n 個整數之間用空格隔開。

【輸出格式】

????????輸出一個整數，表示來回兩條路上參與傳遞紙條的學生的好心程度之和的最大值。

?【數據范圍】

????????1≤n,m≤50

【輸入樣例】

3 3
0 3 9
2 8 5
5 7 0

【輸出樣例】

34

【解題思路】

? ? ? ? 和上面一題類似，多了一個路徑不可重復，考慮一下用上面的方法做一下得到兩條路徑，如果路徑沒有交叉和重疊點那么上面的就是答案。如果有交叉呢。

????????對于有交叉的我們可以通過移動變到沒有交叉但是個別點重合。對于重復，我們必然可以在兩條路線中找到額外的一條或兩條路線，使得新的路線不發(fā)生重合。如下圖：

????????由于原路線是最優(yōu)解，則必然 wA=wB=0，否則最優(yōu)解路徑必然是經過A或B的，因此，我們可以通過微調其中的一條路線，使之不經過重合點 C，同時路線的總價值沒有減少。所以可以直接用方格取數的方法。

【Python程序代碼】

n,m = map(int,input().split())
a = [[0]*(m+5)]
for i in range(n):
    a.append([0]+list(map(int,input().split())))
f = [[[0]*(n+5) for i in range(n+5)] for j in range(n+m+5)]
for k in range(2,n+m+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if k-i>m or k-i<=0 or k-j>m or k-j<=0:continue
            t = f[k][i][j]
            v = a[i][k-i]
            if i!=j:v+=a[j][k-j]
            t = max(t, f[k-1][i-1][j-1])
            t = max(t, f[k-1][i-1][j])
            t = max(t, f[k-1][i][j-1])
            t = max(t, f[k-1][i][j])
            f[k][i][j] = t+v
print(f[n+m][n][n])

到了這里，關于動態(tài)規(guī)劃入門（數字三角形模型）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！