NOIP2008 传纸条（DP及滚动数组优化）

这道题有好多好多种做法呀……先说一下最暴力的，O（n^4的做法）

我们相当于要找两条从左上到右下的路，使路上的数字和最大。所以其实路径从哪里开始走并不重要，我们就直接假设全部是从左上出发的好啦。设dp[i][j][p][q]表示第一条路枚举到点(i,j)，第二条路枚举到点(p,q)时，当前能取到的最大值。

这样dp方程很显然，就是dp[i][j][p][q] = max(dp[i-1][j][p-1][q],dp[i][j-1][p-1][q],sp[i-1][j][p][q-1],dp[i][j-1][p][q-1]) + a[i][j] + a[p][q].如果i==p && j == q，那么减去一个a[i][j].最后dp[m][n][m][n]即为结果。

四层循环枚举，复杂度O（n^4），上一下代码。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#define rep(i,a,n) for(ll i = a;i <= n;i++)

#define per(i,n,a) for(ll i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

const int M = ;

typedef long long ll;

int read()

{

    int ans = ,op = ;

    char ch = getchar();

    while(ch < '' || ch > '')

    {

        if(ch == '-') op = -;

        ch = getchar();

    }

    while(ch >= '' && ch <= '')

    {

        ans *= ;

        ans += ch - '';

        ch = getchar();

    }

    return ans * op;

}

int m,n,dp[][][][],a[][];

int main()

{

    m = read(),n = read();

    rep(i,,m)

    rep(j,,n) a[i][j] = read();

    rep(i,,m)

    rep(j,,n)

    rep(p,,m)

    rep(q,,n)

    {

        dp[i][j][p][q] = max(max(dp[i-][j][p-][q],dp[i-][j][p][q-]),max(dp[i][j-][p-][q],dp[i][j-][p][q-])) + a[i][j] + a[p][q];

        if(i == p && j == q) dp[i][j][p][q] -= a[i][j];

    }

    printf("%d\n",dp[m][n][m][n]);

    return ;

}

之后我们说一下怎么优化。两条路在走的时候，因为每次只能向右或者下走一格，所以两者必然是在同一条斜对角线上的（一条从右上到左下的对角线）那么我们就可以用对角线的横纵坐标和来表示当前DP到了哪里，之后每次只要枚举两个点的横坐标就可以把路径表示出来（也就是表示出来当前枚举的是哪两个点）。这样的话就可以把DP过程的时空降到三维的。

具体的写法也很简单，直接看一下代码即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<queue>

#include<cstring>

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

typedef long long ll;

const int M = ;

int n,m,f[M][M],dp[][M][M],q[M];

int read()

{

    int ans = ,op = ;

    char ch = getchar();

    while(ch < '' || ch > '')

    {

    if(ch == '-') op = -;

    ch = getchar();

    }

    while(ch >='' && ch <= '')

    {

    ans *= ;

    ans += ch - '';

    ch = getchar();

    }

    return ans * op;

}

int main()

{

    m = read(),n = read();

    rep(i,,m)

    rep(j,,n) f[i][j] = read();

    rep(i,,n+m)

    {

    rep(p,,i-)

    {

            if(p > m) break;

        rep(q,,i-)

        {

                if(q > m) break;

        dp[i][p][q] = max(max(dp[i-][p][q-],dp[i-][p-][q]),max(dp[i-][p-][q-],dp[i-][p][q])) + f[p][i-p] + f[q][i-q];

        if(p == q) dp[i][p][q] -= f[p][i-p];

        }

    }

    }

    printf("%d\n",dp[n+m][m][m]);

    return ;

}

之后，时间复杂度基本已经不能再优化，不过空间复杂度却可以优化到O（n^2）（其实还要再乘以一个常数）

我们从刚才的三维DP的转移过程来考虑一下。每次DP都是从上一条对角线上的元素转移过来，和其他的对角线没有任何关系，相当于我们在每次DP的时候只需要考虑两个，一个是i，一个是i-1，在i-1之前的其实已经没有了任何作用。所以我们完全可以废物再利用。因为每次i的值只改变1，所以可以使用按位与的方法把它变成0或者1，之后直接dp即可，而最后的答案就是dp[(m+n)&1][m][m].这样空间复杂度又会降一维。本题的数据范围小，如果数据范围较大，滚动数组对于空间的节省就极为有用了。

看一下代码。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<queue>

#include<cstring>

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

typedef long long ll;

const int M = ;

int n,m,f[M][M],dp[][M][M];

int read()

{

    int ans = ,op = ;

    char ch = getchar();

    while(ch < '' || ch > '')

    {

    if(ch == '-') op = -;

    ch = getchar();

    }

    while(ch >='' && ch <= '')

    {

    ans *= ;

    ans += ch - '';

    ch = getchar();

    }

    return ans * op;

}

int main()

{

    m = read(),n = read();

    rep(i,,m)

    rep(j,,n) f[i][j] = read();

    rep(i,,n+m)

    {

    rep(p,,i-)

    {

        if(p > m) break;

        rep(q,,i-)

        {

        if(q > m) break;

        int k = (i-)&;

        dp[i&][p][q] = max(max(dp[k][p][q-],dp[k][p-][q]),max(dp[k][p-][q-],dp[k][p][q])) + f[p][i-p] + f[q][i-q];

        if(p == q) dp[i&][p][q] -= f[p][i-p];

        }

    }

    }

    printf("%d\n",dp[(n+m)&][m][m]);

    return ;

}

巴特西

NOIP2008 传纸条（DP及滚动数组优化）

最新文章

热门文章