数字三角形模型

摘花生

题目链接： 摘花生

#include <iostream>

using namespace std;

const int N = 110;

int f[N][N],w[N][N];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int r,c;
        cin>>r>>c;
        for(int i = 1;i <= r;i++)
        {
            for(int j = 1;j <= c;j++)
            {
                cin>>w[i][j];
            }
        }

        for(int i = 1;i <= r;i++)
        {
            for(int j = 1;j <= c;j++)
            {
                f[i][j] = max(f[i - 1][j] + w[i][j],f[i][j - 1] + w[i][j]);//只能往左走和往右走
            }
        }

        cout<<f[r][c]<<endl;
    }
    return 0;
}

最低通行费

题目链接： 最低通行费

题目要求在（2n-1）单位时间内穿越出去，不算起点一开始的穿行，横向穿行（n-1）次，纵向穿行（n - 1）次，算上起点就是（2n - 1) 次，满足题目要求，实际含义就是，只能往右或者往下走。

特判（1，1），上边界和左边界

（1，1）：因为是左上角为起点，花费的费用就是w[1][1]

上边界：上边界不能从上方下来

左边界：左边界不能从左边过来

#include <iostream>

using namespace std;
const int N = 110;

int f[N][N],w[N][N];

int main()
{
    int n;
    cin>>n;

    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            cin>>w[i][j];
        }
    }

    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            if(i == 1 && j == 1)
            {
                f[i][j] = w[i][j];
            }
            else
            {
                f[i][j] = 0x3f3f3f3f;//求最小值，初始值最大化
                if(i > 1) f[i][j] = min(f[i][j],f[i - 1][j] + w[i][j]);
                if(j > 1) f[i][j] = min(f[i][j],f[i][j - 1] + w[i][j]);
            }

        }
    }

    cout<<f[n][n]<<endl;
    return 0;
}

方格取数

题目链接： 方格取数

初始想法：

f[i1][j1][i2][j2]表示从（1，1）（1，1）分别走到（i1,j1）（i2, j2）的最大值

因此有一个问题是：“如何处理同一个格子不能被重复处理呢？”

思考：由于只能向下走或者向右走，因此两条路径走到同一个格子表示，走过的步数相同：

​ i1 + j1 == i2 + j2

​ 因此可以想出一个优化版本的f数组：f[k] [i1] [i2] 表示从（1，1）（1，1）分别走到（i1,k - i1）（i2, k - i2）的最大值且走过的步数为k。

因为是两种路径，且每种路径有两种状态转移，则得到2 * 2 = 4种状态转移：

路径：a ,b

a上b上：x = max(x,f[k - 1] [i1 - 1] [i2 - 1] + t);

a上b左：x = max(x,f[k - 1] [i1 - 1] [i2] + t);

a左b上：x = max(x,f[k - 1] [i1] [i2 - 1] + t);

a左b左：x = max(x,f[k - 1] [i1] [i2] + t);

注意：i1 == i2的时候代表走到同一个格子，因为k步数是一样的，j1 = k - i1,j2 = k - i2,得到坐标（i1,j1）（i2,j2）是一样的

#include <iostream>

using namespace std;
const int N = 15;

int f[N + N][N][N],w[N][N];

int main()
{
    int n;
    cin>>n;

    int a,b,c;
    while(cin>>a>>b>>c,a && b && c) w[a][b] = c;

    for(int k = 2;k <= n + n;k++)
    {
        for(int i1 = 1;i1 <= n;i1++)
        {
            for(int i2 = 1;i2 <= n;i2++)
            {
                int j1 = k - i1,j2 = k - i2;
                if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
                {
                    int t = w[i1][j1];//重合时，加任意一个就行
                    if(i1 != i2) t += w[i2][j2];//不重合时，再加上另外一个
                    int &x = f[k][i1][i2];//简化代码
                    x = max(x,f[k - 1][i1 - 1][i2 - 1] + t);//四种状态求最大值
                    x = max(x,f[k - 1][i1 - 1][i2] + t);
                    x = max(x,f[k - 1][i1][i2 - 1] + t);
                    x = max(x,f[k - 1][i1][i2] + t);
                }
            }
        }
    }

    cout<<f[n + n][n][n]<<endl;
    return 0;
}

传纸条

题目链接： 传纸条

#include <iostream>

using namespace std;
const int N = 55;

int w[N][N],f[N * 2][N][N];
int main()
{
    int m,n;
    cin>>m>>n;
    for(int i = 1;i <= m;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            cin>>w[i][j];
        }
    }

    for(int k = 2;k <= m + n;k++)
    {
        for(int i1 = 1;i1 <= m;i1++)
        {
            for(int i2 = 1;i2 <= m;i2++)
            {
                int j1 = k - i1,j2 = k - i2;
                if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
                {
                    int t = w[i1][j1];
                    if(i1 != i2) t += w[i2][j2];

                    int &x = f[k][i1][i2];
                    x = max(x,f[k - 1][i1 - 1][i2 - 1] + t);
                    x = max(x,f[k - 1][i1][i2] + t);
                    x = max(x,f[k - 1][i1 - 1][i2] + t);
                    x = max(x,f[k - 1][i1][i2 - 1] + t);
                }
            }
        }
    }

    cout<<f[n + m][m][m]<<endl;
    return 0;
}