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)\) 盆。

那么就可以得到：

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

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种花的数量)\)。

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)\) 格子所能覆盖到的最大数字和，转移即可。

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