坐标类DP

· · 题解

坐标类DP

例题引入

例1

这里k和L的取值很重要，其实也就是判断从这个方向来的是不是最佳路径。

注意：判断参数时两个if互不干扰。

例2

题目见P1006

题目节选：

小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。

一来一回的要求说明贪心思想不可行： 那么既然光路可逆路线可逆，那么就视为两张一起传。
其实说得直接一点，题目所求就是两条加在一起最大而无重叠的路线。

所以审清题后，我们推出这个图应该长这样：

用dp实现就是计算目前的最大值。于是要表示两张纸条的坐标，可以定义f(i1,j1,i2,j2)为当前最大值。所以推状态转移方程：

f(i1-1,j1,i2-1,j2) \\ f(i1-1,j1-1,i2-1,j2) \\ f(i1-1,j1,i2-1,j2-1) \\ f(i1-1,j1-1,i2-1,j2-1) \end{cases}

不过四维多少大了点，试试降维。用f(k,i,j)表示当前最大值。k=step,i=x1,j=x2。所以y1=k-i,y2=k-j。状态转移方程略（类比降维前，很好理解）。

代码：

#include<bits/stdc++.h>
using namespace std;

int m,n;
int c[107][107];
long long f[107][107][107];

int main()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>c[i][j];
        }
    }
    f[1][2][1]=f[1][1][2]=c[2][1]+c[1][2];
    for(int k=2;k<m+n-1;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i!=j||k==m+n-2)
                {
                    if(k-i+2<=m&&k-j+2<=m&&i<=k+1&&j<=k+1)
                    {
                        f[k][i][j]=max(f[k-1][i][j],max(f[k-1][i-1][j],max(f[k-1][i][j-1],f[k-1][i-1][j-1])))+c[k-i+2][i]+c[k-j+2][j];
                        //cout<<"k="<<k<<" i="<<i<<" j="<<j<<" f="<<f[k][i][j]<<endl;   
                    }   
                }
            }
        }
    }
    f[m+n-1][n][n]=max(f[m+n-2][n][n],max(f[m+n-2][n-1][n],max(f[m+n-2][n][n-1],f[m+n-2][n-1][n-1])));
    cout<<f[m+n-1][n][n]<<endl;
    return 0;
}

注意：