ABC358

E - Alphabet Tiles

https://atcoder.jp/contests/abc358/tasks/abc358\_e

方案数DP。

先看摆花（五年前做过）。

记 (f_{i,j}) 表示摆完前 (i) 种花，目前已经有了 (j) 盆花的方案数。

可以考虑先枚举当前摆第 (i) 种花，然后再枚举摆完第 (i) 种花之后，目前已经有了 (j) 盆花。

不难发现，这种情况下，第 (i) 种花有可能摆了 (0, 1, 2, \ldots, \min(a_i, j)) 盆。

那么就可以得到：

[f_{i,j}=(f_{i-1,j}+f_{i-1,j-1}+…+f_{i-1,j-\min(a_i, j)})(f_{0,0}=1)
]

接下来还能滚动优化，从大到小枚举即可，不过我就不接着优化了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
signed main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, m; std::cin >> n >> m;
    std::vector<int> a(n); for (auto& x : a) {std::cin >> x;}
    std::vector<Z> dp(m + 1); dp[0] = 1;
    for (int i = 0; i < n; i++) {
        std::vector<Z> ndp(m + 1);
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= a[i] and j + k <= m; k++) {//枚举这种花最多能放几盆
                ndp[j + k] += dp[j];//习惯正推
            }
        }
        dp = ndp;
    }
    std::cout << dp[m] << '\n';
    return 0;
}

再来看这道题，其实也是摆花（字母），但是第 (i) 种字母可以随便插入位置，（而不是像本题一样同一种只能放在同一个位置），所以方案数是前 (i - 1) 种花的方案数乘以能插入这第 (i) 种花的位置方案数，即 (\binom{n}{k}(n为当前字符串长度，k为要插入的第i种花的数量))。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
signed main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int K; std::cin >> K;
    std::vector<Z> dp(K + 1);
    dp[0] = 1;
    for (int i = 0; i < 26; ++i) {
        int C; std::cin >> C;
        std::vector<Z> ndp(K + 1);
        for (int j = 0; j <= K; ++j) for (int k = 0; k <= C and j + k <= K; ++k) {
            ndp[j + k] += dp[j] * comb.C(j + k, k);//n = j + k
        }
        dp = ndp;
    }
    std::cout << std::accumulate(dp.begin() + 1, dp.end(), Z(0)) << '\n';
    return 0;
}

答案是 (\sum_{i = 1}^K dp_i)，因为他要求长度为 (1) 到 (K) 之间的字符串的方案数。

G - AtCoder Tour

https://atcoder.jp/contests/abc358/tasks/abc358\_g

贪心简化DP

先用贪心简化题目：

  • 显然会停留在一个最大的（路径中的最大），然后不断重复停留。
  • 显然到达最大的（路径中的最大）的之前，路径中不会有环，也就是整个路径中不会有环。

然后设计状态 (dp_{k, i, j}) 为第 (k) 步走到 ((i, j)) 格子所能覆盖到的最大数字和，转移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
signed main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int H, W, K; std::cin >> H >> W >> K;
    const int N = H * W, Final_k = std::min(K, N);
    int Si, Sj; std::cin >> Si >> Sj; --Si; --Sj;
    std::vector a(H, std::vector<int>(W)); for (auto& vec : a) for (auto& x : vec) {std::cin >> x;}
    std::vector dp(N + 1, std::vector(H + 1, std::vector<i64>(W + 1, -1))); dp[0][Si + 1][Sj + 1] = 0;

    for (int k = 0; k < Final_k; k++) for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {//这里第一重循环必须是K，要先把所有坐标的K - 1步处理出来才能保证答案正确
        for (const auto&[dx, dy] : {std::make_pair(0, 1), {0, -1}, {1, 0}, {-1, 0}, {0, 0}}) {//要么相邻的走过来，要么自己停留不动
            int tx = i + dx, ty = j + dy;
            if (tx < 0 or tx >= H or ty < 0 or ty >= W or dp[k][tx + 1][ty + 1] == -1) {continue;}
            dp[k + 1][i + 1][j + 1] = std::max(dp[k + 1][i + 1][j + 1], dp[k][tx + 1][ty + 1] + a[i][j]); 
        } 
    }
	//枚举在哪里之后无限停留
    i64 ans = 0;
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {ans = std::max(ans, dp[Final_k][i + 1][j + 1] + 1LL * a[i][j] * (K - Final_k));}//在(i, j)停留的最大值
    std::cout << ans << '\n';
    return 0;
}