洛谷 P5664 题解

admin 2021-07-01 AM 156℃ 0条

题目链接

分析

先说一下 84pts 的做法(自己想的)。

Emiya 和 Rin 的要求很好满足,但是 Yazid 的要求有点不好处理。

观察到一个比较关键的性质:出现次数超过一半的主要食材最多只有一种。

考虑容斥,用所有方法数减去不符合条件的方法数。

设 $s_i=\sum_{j=1}^ma_{i,j}$,所有方案数(满足 Emiya 和 Rin 的要求)为 $\Pi_{i=1}^n(s_i+1)-1$。

枚举出现次数超过一半的主要食材。

出现次数超过一半等价于出现次数比其它食材出现次数要多。

设出现次数超过一半的食材编号为 $j$,$dp_{i,k,l}$ 表示前 $i$ 种烹饪方法种使用 $k$ 次 $j$ 号食材,使用 $l$ 次其他食材的方案数。

转移方程:$dp_{i,k,l}=dp_{i-1,k,l}+dp_{i-1,k-1,l}\times a_{i,j}+dp_{i-1,k,l-1}\times(s_i-a_{i,j})$。

边界条件:$dp_{0,0,0}=1$。

答案:所有满足 $k,l\in Z^+,0<k+l\le n,k>l$ 的 $dp_{n,k,l}$ 之和。

时间复杂度 $O(n^3m)$,能过 84% 的数据。代码如下:

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 105, M = 2e3 + 5, P = 998244353;
int a[N][M], s[N], dp[N][N][N], n, m, ans = 1;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]), s[i] = (s[i] + a[i][j]) % P;
        ans = 1LL * ans * (s[i] + 1) % P;
    }
    ans--;
    for (int j = 1; j <= m; j++)
    {
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; i++)     // 前 i 种烹饪方法
            for (int k = 0; k <= i; k++) // 用了 k 次 j 号食材
                for (int l = 0; l <= i - k; l++)
                {                                  // 用了 l 次其它食材
                    dp[i][k][l] = dp[i - 1][k][l]; // 不使用第 i 种烹饪方法
                    if (k)                         // 使用 j 号食材
                        dp[i][k][l] = (dp[i][k][l] + 1LL * dp[i - 1][k - 1][l] * a[i][j]) % P;
                    if (l) // 使用其他食材
                        dp[i][k][l] = (dp[i][k][l] + 1LL * dp[i - 1][k][l - 1] * (s[i] - a[i][j])) % P;
                }
        for (int k = 0; k <= n; k++)
            for (int l = 0; l <= n; l++)
                if (k > l && k + l >= 1)
                    ans = (ans - dp[n][k][l] + P) % P;
    }
    cout << ans << endl;
    return 0;
}

接下来讲满分做法(看了一下题解)。

考虑优化 DP 过程。

我们只需要 $k>l$,也就是 $k-l>0$,不妨拿 $k-l$ 当作状态。

设 $dp_{i,k}$ 表示前 $i$ 种烹饪方法中,选 $j$ 号食材的次数比选其他食材的次数多 $k$ 的方案数。

转移方程:$dp_{i,k}=dp_{i-1,k}+dp_{i-1,k-1}\times a_{i,j}+dp_{i-1,k+1}\times (s_i-a_{i,j})$。

边界条件:$dp_{0,0}=1$。

答案:$\sum_{i=1}^ndp_{n,i}$。

注意 $k-l$ 可能是负数,所以数组下标统一加上 $n$。

解决

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 105, M = 2e3 + 5, P = 998244353;
int a[N][M], s[N], dp[N][N << 1], n, m, ans = 1;

void read(int &ret)
{
    ret = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        ret = ret * 10 + ch - '0', ch = getchar();
}

signed main()
{
    read(n), read(m);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            read(a[i][j]), s[i] = s[i] + a[i][j] >= P ? s[i] + a[i][j] - P : s[i] + a[i][j];
        ans = 1LL * ans * (s[i] + 1) % P;
    }
    ans--;
    for (int j = 1; j <= m; j++)
    {
        dp[0][n] = 1;
        for (int i = 1; i <= n; i++)             // 前 i 种烹饪方法
            for (int k = n - i; k <= n + i; k++) // 选 j 号食材次数 - 选其他食材次数 = k - n
                dp[i][k] = (dp[i - 1][k] + 1LL * dp[i - 1][k - 1] * a[i][j] +
                            1LL * dp[i - 1][k + 1] * (s[i] - a[i][j]) % P + P) %
                           P;
        for (int k = n + 1; k <= n + n; k++)
        {
            ans -= dp[n][k];
            if (ans < 0)
                ans += P;
        }
    }
    cout << ans << endl;
    return 0;
}
标签: 动态规划, CSP-S

非特殊说明,本博所有文章均为博主原创。

评论啦~