AtCoder Beginner Contest 232(E,F补题)_atcoder beginner contest 232 e - rook path

E - Rook Path

题意：

给定大小为$H\times W$的矩阵，你现在有一个车(在矩阵可以朝着一个方向走任意距离)，现在起点为$(x_1,y_1)$,终点$(x_2,y_2)$，你现在只可以恰好移动$k$次，问从起点移动到终点的方案数为多少？

思路：

对于横和纵分别定义一个$dp$方程，把一个二维的移动看成两个一维的移动，分别定义为$X(i,0/1),Y(i,0/1)$
以$X(i,0/1)$为例，代表移动了$i$次后，是否到达了终点的方案数(只考虑$x$轴)，$0$代表未到达，$1$代表到达了
那么此时状态转移方程
$X(i,1)=X(i-1,0)$
$X(i,0)=X(i-1,0)\times (n-2)+X(i-1,1)\times (n-1)$
$Y$同理
最后就是遍历所有的$X(i,1)和Y(k-i,1)$，把两个一维的方案相乘，再乘上一个组合数$C_k^i$，来确定这两个一维方案的移动顺序

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
const int mod = 998244353;
#define ll long long
int n, m, k, X1, Y1, X2, Y2;
ll x[N][2], y[N][2], fact[N], infact[N];
ll qmi(int a, int k, int p) {
    ll res = 1;
    while (k) {
        if (k & 1) res = (ll)res * a % p;
        k >>= 1;
        a = (ll)a * a % p;
    }
    return res;
}
void Init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = (ll)fact[i - 1] * i % mod;
        infact[i] = (ll)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

ll C(int a, int b) {
    if (a < b) return 0;
    return fact[a] * infact[b] % mod * infact[a - b] % mod;
}

int main() {
    Init();
    scanf("%d%d%d", &n, &m, &k);
    scanf("%d%d%d%d", &X1, &Y1, &X2, &Y2);

    if (X1 != X2) {
        x[0][0] = 1;
    } else {
        x[0][1] = 1;
    }
    if (Y1 != Y2) {
        y[0][0] = 1;
    } else {
        y[0][1] = 1;
    }
    for (int i = 1; i <= k; i++) {
        (x[i][1] += x[i - 1][0]) %= mod;
        x[i][0] += (x[i - 1][1] * (n - 1) % mod + x[i - 1][0] * (n - 2) % mod) % mod;
        x[i][0] %= mod;

        (y[i][1] += y[i - 1][0]) %= mod;
        y[i][0] += (y[i - 1][1] * (m - 1) % mod + y[i - 1][0] * (m - 2) % mod) % mod;
        y[i][0] %= mod;
    }

    ll res = 0;

    for (int i = 0; i <= k; i++) {
        ll temp = x[i][1] * y[k - i][1] % mod;
        res += temp * C(k, i) % mod;
        res %= mod;
    }
    printf("%lld\n", res);
}
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

F - Simple Operations on Sequence

题意：

给定两个长度为$N$的$A$序列和$B$序列，现在有$2$种操作
$1.$使得$A_i$增加$1$或者减少$1$,需要消耗$X$元
$2.$交换$A_i$和$A_{i+1}$的位置，需要消耗$Y$元
可以操作多次，问最少花费多少才能使$A$序列变成$B$序列

思路：

序列长度很小,仅为$18$,所以可以考虑状态压缩
假设现在$A$序列中的数有$i$个已经确定，变成$B$中的前$i$个，当然也可以倒过来，是等效的。
那么现在如何表示$A$中哪$i$个数已经确定下来了,就是通过二进制，也就是状态压缩，通过二进制中的$1$的位置，来表示哪些数已经被确定下来了。那么此时只需要枚举，接下来确定那个数即可，且这个数在当前状态下不能被确定过,此时枚举的就是第$i+1$个数，那么此时的代价就是$|A[i+1]-B[j]|\times X+cnt\times Y$，$cnt$就是把$B_j$移动到$A_{i+1}$位置所需要交换的次数。
所以假设状态就是$state$,$cntS$为确定数的个数,枚举的数是$B_j$，$cnt$是把
$f(state|1<<(j-1))=min(f(state|1<<(j-1)),f(state)+|A[i+1]-B[j]|\times X+cnt\times Y)$
根据下标是从$0$还是$1$开始，调整一下下标即可

拿实例来说的话，

#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 18;
#define ll long long
const ll inf = 2e18;
int n;
ll a[30], b[30];
ll f[N], x, y;
bool c[30];
ll F(int state, int now) {
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if ((state & (1 << (i - 1))) == 0 && i < now) res++;
    }
    return res;
}
int main() {
    scanf("%d%lld%lld", &n, &x, &y);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &b[i]);
    }
    f[0] = 0;
    for (int i = 1; i < (1 << n); i++) {
        f[i] = inf;
    }

    for (int state = 0; state < (1 << n); state++) {
        int cntS = 0;
        for (int j = 1; j <= n; j++) {
            if (state & (1 << (j - 1))) {
                cntS++;
            }
        }

        for (int j = 1; j <= n; j++) {
            if (state & (1 << (j - 1))) continue;
            f[state | (1 << (j - 1))] = min(f[state | (1 << (j - 1))], f[state] + abs(a[cntS + 1] - b[j]) * x + F(state, j) * y);
        }
    }
    printf("%lld\n", f[(1 << n) - 1]);
}

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

To be continued
如果你有任何建议或者批评和补充，请留言指出，不胜感激