P1004 [NOIP2000 提高组] 方格取数

基本思路

我想的是搞两次二维 DP 第一次搞完之后把走过的删掉，然后搞第二次，然而只有 \(80pts\)

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

int n;
int x, y, t;
int a[11][11];
int dp1[11][11],dp2[11][11];
pair<int , int> g[11][11];

int main()
{
	cin >> n;
	while(cin >> x >> y >> t)
	{
		if (x == 0 && y == 0 && t == 0) break;
		a[x][y] = t;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (dp1[i - 1][j] + a[i][j] > dp1[i][j - 1] + a[i][j])
			{
				dp1[i][j] = dp1[i - 1][j] + a[i][j];
				g[i][j] = {i - 1, j};
			} 
			else 
			{
				dp1[i][j] = dp1[i][j - 1] + a[i][j];
				g[i][j] = {i, j - 1};
			}
		}
	}
	int i = n, j = n, tx, ty;
	a[n][n] = 0;
	while(g[i][j].first != 0 || g[i][j].second != 0)
	{
		tx = g[i][j].first, ty =g[i][j].second;
		a[tx][ty] = 0;
		i = tx, j = ty;	
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			dp2[i][j] = max(dp2[i - 1][j] + a[i][j], dp2[i][j - 1] + a[i][j]);
		}
	}
	cout << dp1[n][n] + dp2[n][n];
	return 0;
}

证伪

理论错误

• 题意要求两次走过的和最大。

  • 即对两次走过整个过程的动态规划

• 而我的做法是以第一次为第一关键字， 第二次为第二关键字定义下的最大。

  • 即分开对每次动态规划，对总过程实际上是贪心。

例子

• 我的做法
  • 第一次取 $ 2 + 2 = 4$
  • 第二次只能取 \(1\)
  • 总和为 \(5\)
• 正确做法
  • 第一次取 $2 + 1 = 3 $
  • 第二次取 $ 1 + 2 = 3$
  • 总和为 \(6\)

改进思路

两条路同时动态规划

• 状态方程

  • \(F_{x_1,y_1,x_2,y_2}\) 表示第一条路走到 \((x_1, y_1)\)，第二条路走到 \((x_2, y_2)\)时的最优解。

• 状态转移

  \[F_{x_1, y_1, x_2, y_2} = \max(F_{x_1 - 1, y_1, x_2 - 1, y_2} , F_{x_1 - 1, y_1, x_2, y_2 - 1} , F_{x_1, y_1 - 1, x_2 - 1, y_2}, F_{x_1, y_1 - 1, x_2, y_2 - 1}) + map_{x_1, y_1} + map_{x_2, y_2} \]
  • 当然，如果两条路走到同一处就会加两次 \(map\)，要特判减去一次。

AC代码

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

int MAX(int a, int b, int c, int d)
{
	return max(max(a,b),max(c,d));
}

int n;
int x, y, t;
int a[11][11];
int F[11][11][11][11];

int main()
{
	cin >> n;
	while(cin >> x >> y >> t)
	{
		if (x == 0 && y == 0 && t == 0) break;
		a[x][y] = t;
	}
	for (int x1 = 1; x1 <= n; x1++)
	{
		for (int y1 = 1; y1 <= n; y1++)
		{
			for (int x2 = 1; x2 <= n; x2++)
			{
				for (int y2 = 1; y2 <= n; y2++)
				{
					F[x1][y1][x2][y2] = MAX(F[x1 - 1][y1][x2 - 1][y2], F[x1 - 1][y1][x2][y2 - 1], F[x1][y1 -1][x2 -1][y2], F[x1][y1 - 1][x2][y2 - 1]) + a[x1][y1] + a[x2][y2];
					if (x1 == x2 && y1 == y2) F[x1][y1][x2][y2] -= a[x1][y1];
				}
			}
		}
	}
	cout << F[n][n][n][n];
	return 0;
}