Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

CF14E Camels

发表于 分类于
本文字数： 3.9k 阅读时长 ≈ 4 分钟
标签：    

LuoGu: CF14E Camels

CF: E. Camels

暴力DP。

考虑暴力DP，$f _ {p, i, j, s, t}$ 表示在第 $p$ 个位置，上一个位置选择了 $i$ ，再上一个位置选择了 $j$ ，满足第一个条件的个数为 $s$ ，满足第二个条件的个数为 $t$ ，那么可以写出转移方程：
$$
f _ {p, i, j, s + (j > k \wedge j > i), t + (j < k \wedge j < i)} = \sum f _ {p - 1, j, k , s, t}
$$

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
typedef long long LL;
const int N = 30, M = 20;
int n, m;
LL f[N][4][4][M][M];
int main ()
{
    read(n, m);
    if (n < 3) return puts("0"), 0;
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 4; ++j)
            if (i ^ j) ++f[2][i][j][0][0];
    for (int p = 3; p <= n; ++p)
        for (int i = 0; i < 4; ++i)
            for (int j = 0; j < 4; ++j)
                for (int k = 0; i ^ j && k < 4; ++k)
                    for (int s = 0; j ^ k && s <= m; ++s)
                        for (int t = 0; t < m; ++t)
                            f[p][i][j][s + (j > k && j > i)][t + (j < k && j < i)] += f[p - 1][j][k][s][t];
    LL res = 0;
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 4; ++j)
            res += f[n][i][j][m][m - 1];
    write(res);
    return 0;
}

注意到满足题目要求的个数的性质，重新设计状态，$f _ {p, i, k, j}$ 表示当前在第 $p$ 个位置，当前选择了 $i$ ，考虑处于第 $k$ 个峰的部分，$j = 0$ 表示下降，$j = 1$ 表示上升。写出转移方程，复杂度 $O(n ^ 2)$ :
$$
\begin {cases}
f _ {p, i, k, 0} = \sum _ {j > i} f _ {p - 1, j, k, 0} + f _ {p - 1, j, k , 1} \\
f _ {p, i, k, 1} = \sum _ {j < i} f _ {p - 1, j, k, 1} + f _ {p - 1, j, k - 1, 0}
\end {cases}
$$

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
typedef long long LL;
const int N = 30, M = 20;
int n, m;
LL f[N][4][M][2];
int main ()
{
    read(n, m);
    if (n < 3) return puts("0"), 0;
    f[2][1][1][1] = 1;
    f[2][2][1][1] = 2;
    f[2][3][1][1] = 3;
    for (int p = 3; p <= n; ++p)
        for (int i = 0; i < 4; ++i)
            for (int k = 1; k <= m; ++k)
            {
                for (int j = i + 1; j < 4; ++j)
                    f[p][i][k][0] += f[p - 1][j][k][0] + f[p - 1][j][k][1];
                for (int j = 0; j < i; ++j)
                    f[p][i][k][1] += f[p - 1][j][k][1] + f[p - 1][j][k - 1][0];
            }
    LL res = 0;
    for (int i = 0; i < 4; ++i)
        res += f[n][i][m][0];
    write(res);
    return 0;
}
相关文章