Emiya家今天的饭 NOIP2019 (CSP?) 类DP好题 luoguP5664

luogu题目传送门！

首先，硬求可行方案数并不现实，因为不好求（去年考场就这么挂的，虽然那时候比现在更蒟）。

在硬搞可行方案数不行之后，对题目要求的目标进行转换：可行方案数 = 总方案数 - 不合格方案数。

题目多看几眼，（求最大最小方案数量这种套路），DP无疑。

首先考虑列的限制，发现若有不合法的列，则必然有且只有一列是不合法的：因为不可能有不同的两列数量都超过总数的一半。

于是发现列的合法限制数量可以如此计算：每行选不超过一个的方案数（总数） - 每行选不超过一个，且某一列选了超过一半的方案数（不合法的）。

重新审查思路：总方案数为固定值，我们要DP的，肯定就是不合格方案数。（废话）

首先肯定是要先设计状态。怎么样的东东才算是不合格的呢？

重点：：前 i 行选得比别的列总和还多的那一列是不合法的。（肯定超过一半了）

So，如果枚举每一列并统计该列不合法的情况，设计状态 f[i][j][k][h] ,即为第h列的前i行，该h列选了 j 个，别的列总共选了 k 个。

若设si 为每一行的可选的和，

推出状态转移方程： f_i_,_j_,_k = f_i₋₁_,_j_,_k + a_i_,h∗f_ⁱ_⁻_¹_,_j₋₁,_k + (s_i−a_i_,h)∗f_i₋₁_,_j_,_k₋₁

统计该列不合法数量也很简单： Σ(j > k) f[n][j][k][h]

最后将所有列的不合法数量加起来，就能得到总共的不合法数量了。

即为：num = Σ(h = 1~m)Σ(j > k)f[n][j][k][h]

空间能过得去吗？有点悬。

那就用时间换空间吧：把f的h那一纬去掉，枚举每一行的时候用一个ans统计起来就好了。用完就清空给下一列用。

以为就这么结束了？（D2T1能如此迅速的被A掉也太没面子了吧）

上面做法的复杂度达到了O(MN³）的复杂度，只能拿到84分。M = 500 的几个点过不去。

继续优化呗！！

仔细研究一下，我们DP时的循环时间主要花在了哪里？相当一部分是花在了 j 和 k 上。

但是，这些时间值得吗？不值得。因为，我们的答案和j 和 k 具体是多少没关系啊！

我们要的，只是j > k 这一个判断式。

所以，想办法优化掉枚举j 和 k 这一步骤，直接转化成大小。

于是，设 f[i][j]为第h行，前i行比别的行的数量多了 j 个。

将原来使用某种主要食材的菜看做使用了两次该食材，并为每种烹饪方式加一种名叫 “不选” 的菜，

使其使用了所有的主要食材各一次。所有使用某种主要食材大于n次的方案即为不合法方案。

最后考虑如何求总和？

easy。设 g[i][j]为前i行，总共选了 j 个食材的方案数。方程： g[i][j] = g[i-1][j] + (j > 0 ? g[i-1][j-1] * sum[i][0] : 0);
（初始化g[0][0] = 1)
（注意防止数组炸掉,也可以理解为，选择最小只能为0）。

还没完。（真烦）

在进行DP的过程中，可能会出现负数，因此通通打成　(x + mod) % mod．

同时，在计算合法方案数的时候，也将其反过来处理。防止出现玄学的负数

代码来一波呗

 #include <bits/stdc++.h>

 using namespace std;

 #define N 2010

 #define N1 105

 #define isdigit(c) ((c)>='0'&&(c)<='9')

 #define mod 998244353

 #define ll long long

 inline ll read(){

     ll x = , s = ;

     char c = getchar();

     while(!isdigit(c)){

         if(c == '-')s = -;

         c = getchar();

     }

     while(isdigit(c)){

         x = (x << ) + (x << ) + (c ^ '');

         c = getchar();

     }

     return x * s;

 }

 /*进行反向操作，求出   总方案数 - 不合法方案数*/

 ll sum[N1][N], n, m;   /*sum[i] 为第 i 行的和*/

 ll a[N1][N], f[N1][N1 << ];  /*枚举每一列： 对于这一列的f[i][j]，前i行，比其他列多了j个*/

 ll g[N1][N1];

 int main(){

     n = read(), m = read();

     for(int i = ;i <= n; i++)

         for(int j = ;j <= m; j++){

             a[i][j] = read();

             sum[i][] = (sum[i][] + a[i][j]) % mod;   /*首先处理出每一行的总和*/

         }

     for(int i = ;i <= n; i++)

         for(int j = ;j <= m; j++){

             sum[i][j] = (sum[i][] - a[i][j] + mod) % mod; /*sum[i][j]即为除了这一列之外的一行的和*/

         }

     ll ans = ;

     for(int h = ;h <= m; h++){  /*枚举每一列*/

         memset(f, , sizeof(f)); /*不要忘了清理上一列的废 f */

         f[][n] = ;  /*往上抬 n，防止出现负数*/

         for(int i = ;i <= n; i++){

             for(int j = n - i;j <= n + i; j++){ /* 乘以a： 其实就是为1就+，为0就-*/

                 f[i][j] = ((f[i-][j] + f[i-][j-] * a[i][h]) % mod + (f[i-][j+] * sum[i][h]) % mod) % mod;

             }

         }

         for(int i = ;i <= n; i++)   /*反向处理*/

             ans = (ans + f[n][n+i]) % mod; /*全部方案的和,进行反向处理，防负数*/

     }

     /*g[i][j]: 前i行选了j个数的方案数. 则总和即为 Σg[n][i] (i = 1~n)*/

     g[][] = ;

     for(int i = ;i <= n; i++){

         for(int j = ;j <= n; j++){

             g[i][j] = (g[i-][j] + (j >  ? g[i-][j-] * sum[i][] : ) % mod) % mod;

         } /*g[i][j]: 方案总和由上一行选j个数的方案数 + 上一行少选一个数 * 这一行的数量组成*/

     }

     for(int i = ;i <= n; i++){

         ans = (ans - g[n][i] + mod) % mod;

     }

     printf("%lld\n", mod - (ans % mod)); /*代码中进行的是反向处理(防越界)*/

     return ;

 }

巴特西

Emiya家今天的饭 NOIP2019 (CSP?) 类DP好题 luoguP5664

最新文章

热门文章