[数据结构与算法]每日一题1

洛谷，方格取数

思路：
1.DFS的话如果只是一个人还好说，复杂度是9的阶乘，但是，，2个人（一个人走两次就是两个人）
2.动态规划，两个人怎么走呢，，，

设计DP状态：
DP[i][j][l][k]表示第一次走到（i,j）和第二次到(l.k)的最大值。
那么其实由二维的拓展可以知道
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+map[i][j]

所以拓展到四维

 dp[i][j][l][k]=max(dp[i-1][j][l-1][k],max(dp[i-1][j][l][k-1],max(dp[i][j-1][l-1][k],dp[i][j-1][l][k-1])))+maps[i][j]+maps[l][k];

判断：如果已经重复走过了就不要再走了

   if(i==l&&j==k)
          dp[i][j][l][k]-=maps[i][j];

完整代码

#include <bits/stdc++.h>

using namespace std;
int dp[25][25][25][25];
int main()
{
    int n;
    //freopen("in.txt","r",stdin);
    cin>>n;

    int maps[11][11]={0};
    int x,y,z;
    while(cin>>x>>y>>z)
    {
        if(x==0&&y==0&&z==0)
        {
            break;
        }
        maps[x][y]=z;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int l=1;l<=n;l++)
            {
                for(int k=1;k<=n;k++)
                {
                    dp[i][j][l][k]=max(dp[i-1][j][l-1][k],max(dp[i-1][j][l][k-1],max(dp[i][j-1][l-1][k],dp[i][j-1][l][k-1])))+maps[i][j]+maps[l][k];
                    if(i==l&&j==k)
                        dp[i][j][l][k]-=maps[i][j];
                }
            }
        }
    }
    cout<<dp[n][n][n][n]<<endl;
    return 0;
}

类似的题目：
简单
https://www.luogu.com.cn/problem/P1002
较难
https://www.luogu.com.cn/problem/P1006

都是网格上的dp问题，注意各种问题中的具体情况