UVa 986 How Many?

题目描述

考虑平面整数格 $Z\times Z$ 中的路径，这些路径仅由步骤 $(1,1)$ 和 $(1,-1)$ 组成，并且从不经过 $x$ 轴下方。高度为 $k$ 的峰值定义为路径上纵坐标为 $y=k$ 的点，该点前面紧接一个 $(1,1)$ 步骤，后面紧接一个 $(1,-1)$ 步骤。问题要求计算从 $(0,0)$ 出发、终止于 $(2n,0)$ 且恰好有 $r$ 个高度为 $k$ 的峰值的允许路径数量。

输入格式

输入文件包含多个测试用例，每个测试用例由一行组成，包含自然数 $n$、$r$ 和 $k$，分别定义问题（第一个数字为 $n$，第二个数字为 $r$，最后一个为 $k$）。假设 $1\le n<20$，$0\le r<20$，$1\le k<20$。

输出格式

对于每个测试用例，输出一个单独的整数，表示问题的答案，保证结果小于 $2^{31}$。

样例输入

3 1 2
10 3 2

样例输出

2
2002

题目分析

本题要求统计满足特定条件的格路径数量。路径从 $(0,0)$ 开始，到 $(2n,0)$ 结束，只使用 $(1,1)$ 和 $(1,-1)$ 两种步骤，并且始终保持在 $x$ 轴上方或 $x$ 轴上。这类路径被称为 Dyck 路径的变体，因为步长不是 $(1,1)$ 和 $(1,-1)$ 的典型形式，但通过坐标变换可以转化为标准形式。

关键约束是路径中恰好有 $r$ 个高度为 $k$ 的峰值。峰值定义为路径上的一个点，其纵坐标为 $k$，且该点之前是上升步骤 $(1,1)$，之后是下降步骤 $(1,-1)$。注意，路径的起点和终点也可能成为峰值，但需满足相应条件。

由于 $n<20$，路径的总步数为 $2n$，最大为 $38$。状态空间包括当前位置、剩余步数、已形成的峰值数量以及最后一步的方向。可以使用动态规划或记忆化搜索来统计路径数量。

解题思路

定义状态 $\text{dfs}(x,y,r,\text{from})$，其中 $x$ 表示剩余需要走的步数（从 $2n$ 开始递减），$y$ 表示当前纵坐标，$r$ 表示还需要形成的峰值数量，$\text{from}$ 表示到达当前点的最后一步方向（$\text{LEFT\_UP}$ 表示上一步是 $(1,1)$，$\text{LEFT\_DOWN}$ 表示上一步是 $(1,-1)$）。初始状态为 $\text{dfs}(2n,0,r,\text{LEFT\_UP})$，表示从 $(0,0)$ 出发，剩余 $2n$ 步，需要 $r$ 个峰值，且初始方向视为 $\text{LEFT\_UP}$ 以便处理第一个点可能成为峰值的情况。

在每一步，根据当前方向 $\text{from}$ 决定可选的下一步：

• 如果 $\text{from}=\text{LEFT\_UP}$，表示上一步是上升步骤。此时可以选择继续上升 $(1,1)$ 或下降 $(1,-1)$。如果选择下降，并且当前纵坐标 $y+1$ 等于 $k$，则形成一个高度为 $k$ 的峰值，需要将剩余峰值数 $r$ 减 $1$。
• 如果 $\text{from}=\text{LEFT\_DOWN}$，表示上一步是下降步骤。此时只能选择上升 $(1,1)$，因为下降会导致路径穿过 $x$ 轴下方（除非当前纵坐标大于 $0$，但根据问题约束，路径不能低于 $x$ 轴，因此下降步骤后必须上升）。

边界条件：

• 如果 $r>x/2$，则剩余步数不足以形成所需的峰值数量，返回 $0$。
• 如果 $y\ge 2n$ 或 $y<0$，超出合理范围，返回 $0$。
• 当 $x=0$ 时，检查是否满足 $y=0$、$r=0$ 且 $\text{from}=\text{LEFT\_UP}$，若满足则返回 $1$，否则返回 $0$。

使用记忆化数组 $\text{dp}[x][y][r][\text{from}]$ 存储已计算的状态，避免重复计算。由于 $n<20$，状态数最多为 $40\times 40\times 20\times 2=64000$，计算量很小。

代码实现

// How Many
// UVa ID: 986
// Verdict: Accepted
// Submission Date: 2019-12-08
// UVa Run Time: 0.000s
//
// 版权所有（C）2019，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>

using namespace std;

const int LEFT_UP = 0, LEFT_DOWN = 1;

int dp[64][64][64][2], N, R, K;

int dfs(int x, int y, int r, int from)
{
if (r > x / 2) return 0;
if (y >= 2 * N || y < 0) return 0;
if (x == 0) return y == 0 && r == 0 && from == LEFT_UP;
if (~dp[x][y][r][from]) return dp[x][y][r][from];
int ret = 0;
if (from == LEFT_UP)
{
if (y + 1 == K) ret += dfs(x – 1, y + 1, r – 1, LEFT_DOWN);
else ret += dfs(x – 1, y + 1, r, LEFT_DOWN);
ret += dfs(x – 1, y + 1, r, LEFT_UP);
}
else
{
ret += dfs(x – 1, y – 1, r, LEFT_DOWN);
ret += dfs(x – 1, y – 1, r, LEFT_UP);
}
return dp[x][y][r][from] = ret;
}

int main(int argc, char *argv[])
{
cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

while (cin >> N >> R >> K)
{
memset(dp, –1, sizeof(dp));
cout << dfs(2 * N, 0, R, LEFT_UP) << '\\n';
}

return 0;
}

总结

本题通过记忆化搜索统计满足特定峰值条件的格路径数量。关键在于正确定义状态和转移方程，特别是峰值的判定条件：当从上升步骤转为下降步骤时，若当前高度为 $k$，则形成一个峰值。利用 $n<20$ 的小规模，动态规划可以高效解决问题。代码中使用 memset 初始化记忆化数组，并通过递归实现状态转移，逻辑清晰且易于理解。