题目链接:P1006 传纸条
PS:伤心,又想不出来,看了大神的题解
AC代码:
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,m,f[210][210],a[210][210]; int main() { ll i,j,k; cin>>n>>m; for (i=1;i<=n;++i) for (j=1;j<=m;++j) cin>>a[i][j]; f[1][2]=a[1][2]+a[2][1];//不管怎样都会经过(1,2)和(2,1)先赋初值 //i是当前的点横纵坐标之和 //下面的循环是起码2*3或者3*2棋盘才会进入,如果2*2及以下棋盘已经初定义了 for (i=4;i<n+m;++i)//至于i<n+m我是画草图才理解的 { for (j=min(i-2,n);j>=1;j--) //滚动数组,i层和i-层有关,所以j,k要一直减小而不是增大,防止数据覆盖 {//j=min(i-2,n)是在不超出的情况下找尽量小的能走的位置 for (k=min(i-1,n);k>j;k--) {//k在j右边,所以是i-1 if (j>1) //这里的条件判断貌似是不需要的，但加上更好 { f[j][k]=max(f[j][k],f[j-1][k]); } if (j>1&&k>1) { f[j][k]=max(f[j][k],f[j-1][k-1]); } if (k-1>j)//保证移动前的点没有重合 { f[j][k]=max(f[j][k],f[j][k-1]); } //对于两个都从上边来的,其实是另一对(j,k)的两个都从左边来,所以不用写了 f[j][k]+=a[j][i-j]+a[k][i-k];//把数字带上 } } } cout<<f[n-1][n];//输出左下角左边和上边两个格的数字和就好了 return 0; }
谈谈我对这个思路的理解:
1.我们可以看成两纸条同时从左上角原点出发
2.我们发现对于一个画一条条斜线,斜线上的每个点横坐标加纵坐标的和都相同
而且原点到同一条线上任意点要走的距离相同,那么每走一步,纸条a和纸条b都在一条斜线上
为了防止相遇,我们可以假设b的横坐标k永远大于a的横坐标j
而且,我们用i=n+m,那么任意一点的横坐标=i-纵坐标,纵坐标同理,也就是横坐标+纵坐标=i=n+m
3.那我们用i的变化来表示他们现在走到哪条斜线了,
这样一来,就可以开始递推,而且i只和i-1有关系,这是用滚动数组的前提
4.对于数组f[j,k],我们可以看成a走到(j,i-j),b走到(k,i-k)时捡起的总数字
5.然后赋初值,一开始第一步肯定是一个向右,一个向下,所以:
f[1][2]=a[1][2]+a[2][1];
不管怎样都会经过(1,2)和(2,1)先赋初值
6.循环如何实现
for (i=4;i<n+m;++i)//至于i<n+m我是画草图才理解的 for (j=min(i-2,n);j>=1;j--) //滚动数组,i层和i-层有关,所以j,k要一直减小而不是增大,防止数据覆盖 //j=min(i-2,n)是在不超出的情况下找尽量小的能走的位置 for (k=min(i-1,n);k>j;k--)//k在j右边,所以是i-1
第一维for表示要递推的次数,从4开始是因为如果n,m为1,3就没意义了,而m,n为2,2就已经靠初始化就够了,不需要递推
第二维是考虑纸条a的递推,从大到小是因为每次都要用前面的数据赋值新的数据,所以这样能防止覆盖
第三维和第二维差不多
7.递推式
if (j>1) //这里的条件判断貌似是不需要的，但加上更好 { f[j][k]=max(f[j][k],f[j-1][k]); } if (j>1&&k>1) { f[j][k]=max(f[j][k],f[j-1][k-1]); } if (k-1>j)//保证移动前的点没有重合 { f[j][k]=max(f[j][k],f[j][k-1]); } //对于两个都从上边来的,其实是另一对(j,k)的两个都从左边来,所以不用写了
解释以下,这里分别代表
a从左来,b从左来
a从上来,b从左来
a从左来,b从上来
有人回问那两个都从上来去哪了?额,它其实在另外一个地方被算过了,下面上图解释
红色和蓝色表示两个都从上面来,其实他们就等于黄色的那两个地方的两个都从左边来
还有一个地方要注意的是:a从上来,b从左来,这时候要k-1>j,保证移动前的两个点不是重合的
下面上个图解释一下,下图是错误情况
8.输出结果,只要输出当a,b到最右下角那个点的左边和上面的情况的值就好了
老是写不出来DP,自闭了...