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;
}
证伪
理论错误
-
题意要求两次走过的和最大。
- 即对两次走过整个过程的动态规划
-
而我的做法是以第一次为第一关键字, 第二次为第二关键字定义下的最大。
- 即分开对每次动态规划,对总过程实际上是贪心。
例子
0 | 2 | 1 |
---|---|---|
1 | 2 | 0 |
0 | 0 | 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;
}