https://www.luogu.org/problemnew/show/P1004
这道题分类到简单dp但是感觉一点都不简单……这种做两次的dp真的不是很懂怎么写。假如是贪心做两次，感觉又不能证明这是最优的。
直接看题解，题解要设置4个维度，两个人同时走……但是怎么避免同一个物品被两个人拿呢？
设置dp[i][j][k][l]表示第1个人走到ij，第2个人走到kl能实现的最大的取法，再加一维[p]表示现在已经取了00,01,02,10,11,12,20,21,22个物品，然后dp的内容是一个vector！这样就完美地表达了所有信息了！这样同一个物品只会让一个状态转移到另一个状态，保证不会让这个物品同时被取到！空间复杂度？我为什么要管空间复杂度？这个dp时间复杂度都是和空间复杂度同阶的……省那一点干嘛呢……
好了看了别人的状态设置，找到一个思路，先自己写试试看……
写个鬼哦我去，读错题了，不是只能拿两个物品……我又该睡觉了……
注意两个人是同时走的！假设不是两个人同时走的，那会怎么样呢？那样不仅复杂度上升了n2，而且不能判断当前格子是不是被另一个人的路取过了。
#include<bits/stdc++.h> using namespace std; #define ll long long int dp[10][10][10][10]; int a[10][10]; int main(){ int n; scanf("%d",&n); int x,y,v; while(1){ scanf("%d%d%d",&x,&y,&v); if(x==0&&y==0&&v==0) break; a[x][y]=v; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=n;k++){ for(int l=1;l<=n;l++){ dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])); dp[i][j][k][l]+=a[i][j]; if(i==k&&j==l) ; else dp[i][j][k][l]+=a[k][l]; } } } } printf("%d\n",dp[n][n][n][n]); }
别人的题解说后面还有传纸条和回文的路径，也是这种两边一起做的dp。
原文：https://www.cnblogs.com/Yinku/p/10325524.html