洛谷 P3335 [ZJOI2013]蚂蚁寻路 dp

题目描述
在一个 n*m 的棋盘上，每个格子有一个权值，初始时，在某个格子的顶点处一只面朝北的蚂蚁，我们只知道它的行走路线是如何转弯，却不知道每次转弯前走了多长。
蚂蚁转弯是有一定特点的，即它的转弯序列一定是如下的形式：右转，右转，左转，左转，右转，右转…左转，左转，右转，右转，右转。即两次右转和两次左转交替出现的形式，最后两次右转（最后两次一定是右转）后再多加一次右转。我们还知道，蚂蚁不会在同一个位置连续旋转两次，并且蚂蚁行走的路径除了起点以外，不会到达同一个点多次，它最后一定是回到起点然后结束自己的行程，而且蚂蚁只会在棋盘格子的顶点处转弯。

设k 为蚂蚁左转的次数除以2，当k=0 时，蚂蚁可能行走的路径如下图：
洛谷 P3335 [ZJOI2013]蚂蚁寻路 dp

现在已知棋盘大小、每个格子的权值以及左转次数/2 的值，问蚂蚁走出的路径围出的封闭图形，权值之和最大可能是多少。

输入输出格式

输入格式：
在输入文件ant.in中，第一行三个数n,m,k。意义如题目描述。

接下来一个n 行m 列的整数矩阵，表示棋盘。

输出格式：
一个数，表示蚂蚁所走路径围出的图形可能的最大权值和。

输入输出样例

输入样例#1：
2 5 2
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
输出样例#1：
-8
说明

【样例说明】

除了第一行的第二个和第一行的第四个都要围起来才至少合法。

【数据规模与约定】

10%的数据所有格子中权值均非负

另20%的数据n=2

另30%的数据k=0

100%的数据1≤n≤100,1≤m≤100,0≤k≤10 保证存在合法路径，
数据有梯度，格子中每个元素的值绝对值不超过 10000

分析：
显然合法路径围城的是一个底边是水平的，上边是山字形的一个区域。
我们直接枚举底边是哪一行，然后dp。
设 $f[i][j][k]$ 表示枚举到第 $i$ 列，高度为 $j$ ，当前到第 $k$ 个上端水平位置的和。
然后发现 $k$ 是奇数时可以转移位置是前缀关系，偶数时是后缀关系，直接统计max即可。
复杂度是 $O(n^3k)$ 。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>

const int maxn=107;
const int inf=0x3f3f3f3f;

using namespace std;

int n,m,q,maxx,ans;
int a[maxn][maxn],f[maxn][maxn][25],g[maxn];

int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }	
    ans=-inf;
    for (int l=1;l<=n;l++)
    {
        memset(f,-inf,sizeof(f));		
        for (int i=0;i<=m;i++) f[i][0][0]=0;
        for (int k=1;k<=2*q+1;k++)
        {
            if (k&1)
            {
                for (int i=0;i<=m;i++) g[i]=-inf;
                for (int j=1;j<=l;j++)
                {
                	g[0]=max(g[0],f[0][j-1][k-1]);
                	maxx=g[0]-a[l][0]+a[l-j][0];
                    for (int i=1;i<=m;i++)
                    {
                        g[i]=max(g[i],f[i][j-1][k-1]);
                    	f[i][j][k]=maxx+a[l][i]-a[l-j][i];
                    	maxx=max(maxx,g[i]-a[l][i]+a[l-j][i]);
                    }
                }
            }
            else
            {
                for (int i=0;i<=m;i++) g[i]=-inf;
                for (int j=l;j>0;j--)
                {
                    g[0]=max(g[0],f[0][j+1][k-1]);
                	maxx=g[0]-a[l][0]+a[l-j][0];
                    for (int i=1;i<=m;i++)
                    {
                        g[i]=max(g[i],f[i][j+1][k-1]);
                    	f[i][j][k]=maxx+a[l][i]-a[l-j][i];
                    	maxx=max(maxx,g[i]-a[l][i]+a[l-j][i]);
                    }
                }
            }
        }
        for (int i=1;i<=m;i++)
        {
            for (int j=1;j<=l;j++) ans=max(ans,f[i][j][2*q+1]);
        }
    }
    printf("%d\n",ans);
}

洛谷 P3335 [ZJOI2013]蚂蚁寻路 dp

相关推荐