秋招算法题——线性动态规划——方格取数

问题描述

思路分析

• 这个题有一个误区，很容易想成是两次动态规划，就一定能最优，于是将所有的注意力都放在了如何记录动态规划的路径上。两次各自对应的全局最优，并不一定是两次运动的联合最有，具体见下图。

• 将其考虑成有两个对象同时运动，然后计算两者的联合最优，动态规划的方程应该是f(x1,y1,x2,y2)这样的四维才对，保证两个运动的最优。又因为两个人的时间步骤相同，x1 + y1 = x2 + y2 = k，用k表示时间步骤，所以可以将之降维三维。f（k，x1，x2）进行计算。

• 然后就是状态变换，每一个节点最优，需要同时考虑每一个节点可能来自两个方向，分别是上方和左方，加起来就是4种情况。所以，每一节点的最优值都是由四种情况考虑出来。

提交代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;
int w[N][N];
int f[2*N][N][N];

int main() {
   
    int t;
    cin>>t;
    int n,m,v;
    while(cin>>n>>m>>v,n