Codeforces Beta Round 14 (Div. 2) E. Camels (DP)

题目

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;
}