题目内容

P1006

大意:矩阵中传纸条,左上角传到右下角,再传回去,每个点只能经过一次,求经过的点的好感度的和的最大值

解题思路

这是一个多维的 dp,首先如果真的按照题目模拟的话是极其复杂的,因此可以直接抽象为从原点出发的两个人互不冲突地走。所以每一步移动两个小人的横纵坐标之和是相等的。注意到这条性质之后,dp 的状态就可以只存储两个小人分别的横坐标,因为纵坐标可以直接推出来。

令某一时刻小人的横纵坐标之和为 k,甲小人的横坐标为 i,乙小人的横坐标为 j,则甲小人的纵坐标为 k-i,乙小人的纵坐标为 k-j

f(k,i,j) 表示现在横纵坐标为 k,甲小人的横坐标为 i,乙小人的横坐标为 j 时的最大好感值,由于这一状态的来源只有四种:

  • 甲下,乙下
  • 甲下,乙右
  • 甲右,乙下
  • 甲右,乙右

所以可以列出方程:

f(k,i,j)=\max\lbrace f(k-1,i,j),f(k-1,i-1,j-1),f(k-1,i,j-1),f(k-1,i-1,j) \rbrace+v(i,j)

考虑空间优化:类比背包问题,表示 k 的维度其实是多余的,像背包一样处理即可,从大到小枚举

注意:第二层枚举 j 的时候要注意,我们因为假定甲小人永远在乙小人的左边,所以枚举的时候 j 要大于 i。

代码:

#include <cstdio>
#include <algorithm>
using std::max;

int m,n,map[501][501],f[501][501];

int main()
{
    scanf("%d %d",&m,&n);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&map[i][j]);
    for(int k=3;k<=n+m;k++)//直接从3开始枚举
        for(int i=m;i>=1;i--)//从大到小
            for(int j=m;j>i;j--)//从大到小
                f[i][j]=max(max(f[i][j],f[i-1][j-1]),max(f[i][j-1],f[i-1][j])),
                f[i][j]+=map[i][k-i]+map[j][k-j];//这里是加上枚举到的位置的同学的好感度
    printf("%d\n",f[m-1][m]);//第一维是m-1的原因是i恒小于j,同时最后一个点的好感度没有影响
    return 0;
}
最后修改日期:2020年3月4日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。