洛谷 P1006 [NOIP2008 提高组] 传纸条

题意：传纸条，跟方格取数一样，但是两条路径不能有重复的。

思路：还是一样的走，但是x1跟x2不能相等，包括现在跟上一个状态。

总结：看了题解，发现题解大多数都是逻辑不正确的，更有离谱的是数组范围都不加特判，数组访问越界但是可以ac的情况，数据太烂了，放个自以为正确的思路吧，发现之前自己提交的满分代码也不是逻辑完全正确，放个自以为正确的代码。

void solve(){
	int n, m;
	cin >> n >> m;

	vector<vector<int>> grid(n + 1, vector<int> (m + 1, 0));
	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= m; ++j){
			cin >> grid[i][j];
		}
	}

	vector<vector<vector<int>>> dp(2, vector<vector<int>> (n + 1, vector<int>(m + 1, 0)));
	dp[0][1][1] = grid[1][1];

	vector<vector<int>> zeros(n + 1, vector<int>(m + 1, 0));
	int cur = 0;
	for (int s = 1; s <= n + m - 2; ++s){
		cur ^= 1;
		for (int x1 = 1; x1 <= min(s + 1, n); ++x1){
			for (int x2 = 1; x2 <= min(s + 1, n); ++x2){
				if (x1 == x2 && (s != n + m - 2)){
					continue;
				}
				int y1 = s + 2 - x1;
				int y2 = s + 2 - x2;
				if (max(y1, y2) > m){
					continue;
				}
				if (x1 > 1 && x2 > 1){
					dp[cur][x1][x2] = max(dp[cur][x1][x2], dp[!cur][x1 - 1][x2 - 1] + grid[x1][y1] + grid[x2][y2]);
				}
				if (x1 > 1 && y2 > 1 && (x1 - 1 != x2 || (x1 == 2 && s == 1) || s == n + m - 2)){
					dp[cur][x1][x2] = max(dp[cur][x1][x2], dp[!cur][x1 - 1][x2] + grid[x1][y1] + grid[x2][y2]);
				}
				if (y1 > 1 && x2 > 1 && (x2 - 1 != x1 || (x2 == 2 && s == 1) || s == n + m - 2)){
					dp[cur][x1][x2] = max(dp[cur][x1][x2], dp[!cur][x1][x2 - 1] + grid[x1][y1] + grid[x2][y2]);
				}
				if (y1 > 1 && y2 > 1){
					dp[cur][x1][x2] = max(dp[cur][x1][x2], dp[!cur][x1][x2] + grid[x1][y1] + grid[x2][y2]);
				}
			}
		}
	}
  //  for (int i = 1; i <= n; ++i){
	  //  for (int j = 1; j <= m; ++j){
	  //      cout <<dp[cur][i][j] << " \n"[j == m];
	   // }
	//}

	cout << dp[cur][n][m]  << '\n';
}