题目
Bob likes to draw camels: with a single hump, two humps, three humps, etc. He draws a camel by connecting points on a coordinate plane. Now he’s drawing camels with t humps, representing them as polylines in the plane. Each polyline consists of n vertices with coordinates (x1, y1), (x2, y2), …, (xn, yn). The first vertex has a coordinate x1 = 1, the second — x2 = 2, etc. Coordinates yi might be any, but should satisfy the following conditions:
- there should be t humps precisely, i.e. such indexes j
(2 ≤ j ≤ n - 1), so that yj - 1 < yj > yj + 1, - there should be precisely t - 1 such indexes j (2 ≤ j ≤ n - 1), so
that yj - 1 > yj < yj + 1, - no segment of a polyline should be parallel to the Ox-axis,
- all yi are integers between 1 and 4.
For a series of his drawings of camels with t humps Bob wants to buy a notebook, but he doesn’t know how many pages he will need. Output the amount of different polylines that can be drawn to represent camels with t humps for a given number n.
Input
The first line contains a pair of integers n and t (3 ≤ n ≤ 20, 1 ≤ t ≤ 10).
Output
Output the required amount of camels with t humps.
Examples
input
6 1
output
6
题解
这道题的状态表示很难想,反正我是看题解的;
首先根据题目中给到的两个未知量 n, t,我们不难想到状态表示中一定是要包含 n 和 t,我们可以猜测状态方程为:
f[i][j] 表示前i个点中,包含j个驼峰的合法的方案数;
但是如何实现状态转移呢?
我们发现只用两维去表示状态无法写出转移方程,因为我们无法知道驼峰的高度,所谓的合法方案无法只被两维状态表示出来,那么我们就要引进新的状态:
用 a, b 表示上一个和上上个点的高度(y值)
因为只有知道了相邻的两个点的高度才能实现状态转移。
同时,我们不光要知道驼峰 j 的个数,还得知道驼谷 k 的个数,这样才能知道哪些方案是合法的,哪些不是。
所以最后的状态表示需要五维。
f[i][j][k][a][b] 表示填前i个y, j个波峰, k个波谷, 第i-1个y是a, 第i个y是b
知道了状态表示,状态转移就很容易写出了,直接写六重循环,分别枚举i,j,k,a,b,c(第i+1个点的y值),看满足驼峰还是满足驼谷,分别加一即可,如果状态不合法,直接延续之前的状态。
代码
#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;typedef long long LL;const int N = 50;int n, t;
int f[22][22][22][5][5];int main()
{cin >> n >> t;for (int i = 1; i <= 4; i++)for (int j = 1; j <= 4; j++)if (i != j) f[2][0][0][i][j] = 1;for (int i = 2; i < n; i++)for (int j = 0; j <= t; j ++)for (int k = 0; k <= t - 1; k++)for (int a = 1; a <= 4; a++)for (int b = 1; b <= 4; b++){if(a != b)for (int c = 1; c <= 4; c++){if (b != c){if (a > b && b < c) f[i + 1][j][k + 1][b][c] += f[i][j][k][a][b]; // 这就是波谷else if (a < b && b > c) f[i + 1][j + 1][k][b][c] += f[i][j][k][a][b];else f[i + 1][j][k][b][c] += f[i][j][k][a][b];}}}LL ans = 0;for (int i = 1; i <= 4; i++)for (int j = 1; j <= 4; j++)ans += f[n][t][t - 1][i][j];cout << ans << endl;return 0;
}