1314：【例3.6】过河卒(noip2002)

过河卒是一道经典的动态规划问题。题目描述为：在一个棋盘上，有一个卒子，它初始位置在左下角，目标位置在右上角。卒子只能向上或向右移动，同时棋盘上有若干个障碍物，卒子不能经过障碍物。求卒子从初始位置到目标位置的路径数。

这道题可以用动态规划来解决。我们可以定义一个二维数组dp，其中dp[i][j]表示卒子从起点(,)到达位置(i,j)的路径数。对于每个位置(i,j)，如果它不是障碍物，则有：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

其中dp[i-1][j]表示从上方到达该位置的路径数，dp[i][j-1]表示从左方到达该位置的路径数。如果该位置是障碍物，则dp[i][j]为。

最终，dp[m][n]即为卒子从起点到达目标位置的路径数，其中m和n分别为棋盘的行数和列数。

需要注意的是，在计算dp数组时，需要先初始化dp[][]为1，因为卒子初始位置就是起点。同时，如果起点或目标位置是障碍物，则路径数为。

相关问题

[NOIP2002]自由落体

自由落体问题是指在高为H的天花板上有n个小球，它们从高处自由下落到地面上的小车上。根据给定的参数，我们需要计算小车接住小球的次数。

为了解决这个问题，可以使用枚举的方法来判断小球何时会被小车接住。我们可以通过计算小球下落的时间和小车到达相应位置的时间来判断是否能够接住小球。具体的步骤如下：

1. 根据给定的参数，包括天花板高度H，小球数量n，小车的长度L，高度K，以及小车距离原点的距离S1。
2. 使用循环遍历每一个小球的位置，从n-1遍历到0。
3. 对于每个小球位置i，判断是否满足小球下落到小车前端和后端的条件。
4. 计算小球下落到小车前端的时间t1和下落到小车后端的时间t2。
5. 判断小球是否能够被小车接住，可以通过比较小球下落的纵坐标和小车的高度来确定。如果满足条件，则计数器cnt加一。
6. 循环结束后，输出计数器cnt的值，即表示小车接住小球的次数。

1309：【例1.6】回文数(noip1999)

题目描述：

如果一个数从左往右读和从右往左读是一样的，那么这个数就是回文数。例如：121、2332、12321都是回文数。

输入格式：

一个整数n(1<=n<=10000)

输出格式：

如果n是回文数，输出YES，否则输出NO。

样例输入：

12321

样例输出：

YES

解题思路：

将输入的整数n转换成字符串，然后判断字符串是否是回文字符串即可。

回文字符串的判断方法：将字符串反转，如果反转后的字符串和原字符串相等，则原字符串是回文字符串。

代码实现：