[数据结构与算法]【acwing】1027. 方格取数****（dp）

2022.3.21更新：关于i1-1,以及i2-1等。
相当于，以
（1，1）作为f[1][i1][i2],
（1，0）为f[1][i1][i2-1];
（0，1）为f[1][i1-1][i2];
（0，0）为f[1][i1-1][i2-1];
f[1][i1-1][i2-1]中的f[1]指k=1，走了一步，也就是在（1,1)这个点。
（这思想太妙了，太绝了。）

穿越隧道

开始的想法是先第一遍走，将走过的值标记。然后，第二次在标记的矩阵中再走一遍。
发现，在第一遍走后进行标记的过程中，会将矩阵中的所有值标记为0.（标记没有准确标记原矩阵中走过的元素，而是将每行中的元素进行判断并且标记，可能是导致走过一边后的矩阵在标记后，原矩阵的值全为0.
后来，发现是4维dp问题，可优化为3维。
初步听了y总课，还需要进一步加深理解

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int f[2*N][N][N];
int n,r,c,v;
int w[N][N];
int main(){
    scanf("%d",&n);
    while(scanf("%d%d%d",&r,&c,&v) && (r || c || v)){
        w[r][c] = v;
    }
    for(int k = 2; k <= 2*n; k++){
        for(int i1 = 1; i1 <= n; i1++){
            for(int i2 = 1; i2 <= n; i2++){
                int j1 = k - i1, j2 = k - i2;
                if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n){
                    int &x = f[k][i1][i2];
                    int t = w[i1][j1];
                    if(i1!=i2){
                        t += w[i2][j2];
                    }
                    x = max(x,f[k - 1][i1 - 1][i2] + t);
                    x = max(x,f[k - 1][i1][i2 - 1] + t);
                    x = max(x,f[k - 1][i1 - 1][i2 - 1] + t);
                    x = max(x,f[k - 1][i1][i2] + t);
                }
            
            }
        }
    }
    cout << f[2*n][n][n] << endl;
    return 0;
}