详解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——传纸条。通过对题目的分析和阐述，以及对动态规划算法的思路和实现进行了解析。最终，呈现出一份完整的代码示例，供读者学习、参考和借鉴。