P1006 传纸条（二维、三维dp）

P1006 传纸条

输入输出样例

输入 #1 复制

3 3

0 3 9

2 8 5

5 7 0

输出 #1 复制

34

说明/提示

【限制】

对于 30% 的数据，1≤m,n≤10； 对于 100% 的数据满1≤m,n≤50

NOIP 2008提高组第三题

思路如下

这一题应该是可以看成由两种解法，但是也可以看成一种解法，题解三四可以看成是题解一 ，优化掉一维的结果。

题解传送门

题解一(四维dp)

#include <iostream>

#define maxn 55

using namespace std;

int f[maxn][maxn][maxn][maxn],a[maxn][maxn];

int n,m;

int max_ele(int a,int b,int c,int d){

    if (b>a)

        a = b;

    if (c>a)

        a = c;

    if (d>a)

        a = d;

    return a;

}

int main(){

    cin >> n >> m;

    for (int i=1;i<=n;i++)

        for (int j=1;j<=m;j++)

                cin >> a[i][j];

    for (int i=1;i<=n;i++)

        for (int j=1;j<=m;j++)

            for (int k=1;k<=n;k++)

                for (int l=j+1;l<=m;l++)

                    f[i][j][k][l]=max_ele(f[i][j-1][k-1][l],f[i-1][j][k][l-1],f[i][j-1][k][l-1],f[i-1][j][k-1][l])+a[i][j]+a[k][l];

    cout << f[n][m-1][n-1][m] << endl;

    return 0;

}

题解二（三维dp）

#include <iostream>

#include <cstring>

#include <cstdio>

#define maxn 55

using namespace std;

int f[2 * maxn][maxn][maxn];

int a[maxn][maxn];

int n,m;

int max_ele(int a,int b,int c,int d){

    if (b>a)

        a = b;

    if (c>a)

        a = c;

    if (d>a)

        a = d;

    return a;

}

int main(){

    cin >> n >> m;

    for (int i=1;i<=n;i++)

        for (int j=1;j<=m;j++)

            cin >> a[i][j];

    for (int k=1;k<=n+m-1;k++)

        for (int i=1;i<=n;i++)

            for (int j=1;j<=n;j++)

            {

                if (k-i+1<1 || k-j+1<1) //这里是判断纵坐标的合法性，如果纵坐标不合法那就跳过去

                    continue;

                 f[k][i][j] = max_ele(f[k-1][i][j],f[k-1][i-1][j-1],f[k-1][i][j-1],f[k-1][i-1][j]) + a[i][k-i+1] + a[j][k-j+1];

                if (i==j) //判断重合路径

                    f[k][i][j]-=a[i][k-i+1];

            }

    cout << f[n+m-1][n][n] << endl;

    return 0;

}

题解三

#include<iostream>

#include<string.h>

using namespace std;

const int Len = 100;

long long int dp[Len*2][Len][Len];

long long int map[Len][Len];

int main()

{

    freopen("T.txt","r",stdin);

    int m,n;

    scanf("%d %d", &m, &n);

    for(int i = 1; i <= m; i ++)

        for(int j = 1; j <= n; j ++)

            scanf("%lld", &map[i][j]);

    //初始化dp

    memset(dp , -1 , sizeof(dp));

    dp[2][1][1] = 0;    //原点好心值为 0

    //核心dp

    for(int i = 3; i < m + n; i ++)

        for(int j = 1; j < n; j ++)

            for(int k = j + 1; k <= n; k ++)

            {

                cout<< i - k<<endl;

                long long int tem = dp[i][j][k];

                if(dp[i - 1][j][k] > tem)   tem = dp[i - 1][j][k];

                if(dp[i - 1][j - 1][k] > tem)   tem = dp[i - 1][j - 1][k];

                if(dp[i - 1][j][k - 1] > tem)   tem = dp[i - 1][j][k - 1];

                if(dp[i - 1][j - 1][k - 1] > tem)   tem = dp[i - 1][j - 1][k - 1];

                if(tem == -1)        //如果tem的值为-1 那么说明这个点是不存在的

                    continue;

                dp[i][j][k] = tem + map[i - j][j] + map[i - k][k];

            }

    printf("%lld\n",dp[m + n - 1][n - 1][n]);

    return 0;

}