詳解p1007

一、基本介紹

1、p1007是什麼

p1007是指洛谷題庫中的題目編號1007，全稱為「傳紙條」。這是一道經典的動態規劃題目，適合練習動態規劃演算法。

2、p1007的難度

p1007被評定為普及/提高-，它的理解難度不高，但需要有較好的動態規劃基礎和較強的編碼能力才能AC它。

二、題意解析

1、題目大意

在一個N×M的方格圖上，每個格子可以寫上一個數字。現在從左上角走到右下角，每次只能向右或向下走，走過的格子上的數字累加起來。求出一條規定的「好」的路徑，使經過的數字的總和最大。

2、輸入格式

N M
a1,1 a1,2 ... a1,M
a2,1 a2,2 ... a2,M
...
aN,1 aN,2 ... aN,M

其中N和M分別為方格圖的行數和列數，ai,j代表第i行第j列的數字。

3、輸出格式

一個整數，代表一條好路徑經過的數字總和的最大值。

三、演算法思路

1、動態規劃思路

設f(i,j,k)表示從起點(1,1)走到(i,j)經過的數字總和為k的路徑數。則有：

f(i,j,k) = f(i-1,j,k-ai,j) + f(i,j-1,k-ai,j)    (k>ai,j)
f(i,j,k) = f(i-1,j,k) + f(i,j-1,k)    (k=ai,j)

其中，(i,j)表示當前所在的格子，k表示從起點走到(i,j)的路徑上所經過的數字總和。

2、演算法實現

計算f(i,j,k)時，需要遞推求出f(i-1,j,k-ai,j)，f(i,j-1,k-ai,j)，f(i-1,j,k)和f(i,j-1,k)，再根據上述公式求解f(i,j,k)。最終結果就是f(N,M,X)，其中X為合法路徑經過的最大數字總和。

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;++i)
        for(int j=1;j> a[i][j];
    memset(f, 0, sizeof(f));
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            for(int k=1;k= a[i][j])
                    f[i][j][k] = f[i-1][j][k-a[i][j]] + f[i][j-1][k-a[i][j]];
                else
                    f[i][j][k] = 0;
                if(i==1 && j==1)
                    f[i][j][a[1][1]] = 1;
    int ans = 0;
    for(int k=a[1][1]+1;k<n+m-1;++k)
        ans += f[n][m][k];
    cout << ans << endl;
    return 0;
}

四、程序代碼

#include <bits/stdc++.h>
using namespace std;

const int N = 55, M = 105;
int f[N][N][M], n, m;
int a[N][N];

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;++i)
        for(int j=1;j> a[i][j];
    memset(f, 0, sizeof(f));
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            for(int k=1;k= a[i][j])
                    f[i][j][k] = f[i-1][j][k-a[i][j]] + f[i][j-1][k-a[i][j]];
                else
                    f[i][j][k] = 0;
                if(i==1 && j==1)
                    f[i][j][a[1][1]] = 1;
    int ans = 0;
    for(int k=a[1][1]+1;k<n+m-1;++k)
        ans += f[n][m][k];
    cout << ans << endl;
    return 0;
}

五、總結

本文詳細介紹了洛谷題庫中的p1007——傳紙條。通過對題目的分析和闡述，以及對動態規劃演算法的思路和實現進行了解析。最終，呈現出一份完整的代碼示例，供讀者學習、參考和借鑒。