洛谷p1006 DP

题目链接：洛谷p1006
题目就是说传两次纸条，一次从左上传到右下，一次从右下传到左上，路径不能重复，其实我们换个角度就是从左上传到右下传两次就可以了。
借助洛谷大佬题解的一张图
你传两次的路径，每一步两个点的连线一定在一条斜线上，那么，其实对于一个矩阵，也就最多只有n+m条斜线，已确定两点在一条线上，那么就比较容易去设计。
我们用f[sum][i][j]，sum表示当前斜线是哪条（就是斜线上任何一个点的横竖坐标的累加，比如sum = 3就是图里面那条斜线），i表示一个人当前走的列的坐标，j表示另一个人当前走的列的坐标。
ij肯定不能相当（因为是在一条线上）。
我们如何转移呢？
思考一下我们是知道了当前两个人分别在那条线，哪两个位置，
那么对于这两个位置都是可以从上方走下来，或者从右边走过去。
也就是,并且从上一步走过来的点一定是上条斜线。
那么就可以转移
(从上方走下来列数是不会改变的所以如果是从上走到下的对应点的列数不变，从右走过去很明显列数是变大了)

1. f[sum][i][j] = max(f[sum-1][i][j]+v)，第一个人是从上方走下来的，第二个人是从上方走下来的。
2. f[sum][i][j] = max(f[sum-1][i][j-1]+v)第一个人是从上方走下来的,第二个人是从右边走过来的
3. f[sum][i][j] = max(f[sum-1][i-1][j]+v)第一个人是从右边走过来的，第二个人是从上方走下来的。
4. f[sum][i][j] = max(f[sum-1][i-1][j-1]+v)第一个人是从右边走过来的，第二个人是从右边走过来的。
   v就是ij各自表示的哪一个点的价值。对于上述转移，要注意的就是什么时候第二维的i和第三维的j都不能相等（在一条斜线上就列数不可能相等）。
   那么最后的结果就是倒数第二条线的权值了（倒数第二条线就两个点，对应两个人位置）。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>;
#include<cstring>
using namespace std;
const long long max_ = 1e7;
inline int read(){
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
int f[100][100][100];
int node[100][100],n,m;
int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			node[i][j] = read();
		}
	}
	for (int sum = 3; sum <= n + m; sum++) {
		for (int i = 1; i <= sum-1; i++) {
			for (int j = 1; j <= (sum - 1); j++) {
				if (i == j)continue;
				if (j - 1 != i)
					f[sum][i][j] = max(f[sum][i][j], f[sum - 1][i][j - 1]+node[sum-i][i] + node[sum-j][j]);
				if (i != j)
					f[sum][i][j] = max(f[sum][i][j], f[sum - 1][i][j] + node[sum - i][i] + node[sum - j][j]);
				if (i - 1 != j - 1)
					f[sum][i][j] = max(f[sum][i][j], f[sum - 1][i - 1][j - 1] + node[sum - i][i] + node[sum - j][j]);
				if (i - 1 != j)
					f[sum][i][j] = max(f[sum][i][j], f[sum - 1][i - 1][j] + node[sum - i][i] + node[sum - j][j]);
			}
		}
	}
	cout << max(f[n + m - 1][m][m - 1], f[n + m - 1][m - 1][m]);
	
	
	return 0;
}