CodeForces 429B【dp】

题意：

在一个n*m的矩阵中有两只虫子，一只从左上角向右下角移动，另外一只从左下角向右上角移动。

要求：

1.第一只虫子每次只能向左或者向下移动一格，另外一只只能向上或者向右移动一格。

2.两只虫子的路径最多只能重合一点。

3.求解两只虫子路径中除去重合那点其余各点的权值之和最大。

思路：

1.显然这题需要枚举所有可能的相交的点。

2.将问题转化成从四个角向可能的交点的四条路的权值最大。

3.为了保证路径只能有一个交点，我们考虑从可能的交点的上面的点通往上侧的两个角，左面的点通往左侧的两个角以此类推（参考大神的思想）。

4.用递推式子f[i][j]=max(f[i-1][j],f[i][j-1])+map[i][j].（这里只是写了其中一种情况（从左上角到该点的情况，其他三种情况类似））。

坑点：

边界上的点一定不可能作为唯一的交点。

#include<stdio.h>

#include<algorithm>

#include<string.h>

using namespace std;

int pho[][];

int pho1[][];

int pho2[][];

int pho3[][];

int pho4[][];

int main()

{

    int n,m;

    memset(pho,,sizeof(pho));

    memset(pho1,,sizeof(pho1));

    memset(pho2,,sizeof(pho2));

    memset(pho3,,sizeof(pho3));

    memset(pho4,,sizeof(pho4));

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

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

    {

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

        {

            scanf("%d",&pho[i][j]);

        }

    }

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

    {

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

        {

            pho1[i][j]=max(pho1[i-][j],pho1[i][j-])+pho[i][j];

        }

    }

    for(int i=n;i>=;i--)

    {

        for(int j=m;j>=;j--)

        {

            pho2[i][j]=max(pho2[i+][j],pho2[i][j+])+pho[i][j];

        }

    }

    for(int i=n;i>=;i--)

    {

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

        {

            pho3[i][j]=max(pho3[i+][j],pho3[i][j-])+pho[i][j];

        }

    }

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

    {

        for(int j=m;j>=;j--)

        {

            pho4[i][j]=max(pho4[i-][j],pho4[i][j+])+pho[i][j];

        }

    }

    int ans=-;

    bool ok=;

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

    {

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

        {

            ans=max(ans,pho1[i-][j]+pho2[i+][j]+pho3[i][j-]+pho4[i][j+]);

            ans=max(ans,pho1[i][j-]+pho2[i][j+]+pho3[i+][j]+pho4[i-][j]);

        }

    }

    printf("%d\n",ans);

}

巴特西

CodeForces 429B【dp】

最新文章

热门文章