题解 P5664 【Emiya 家今天的饭【民间数据】】
_louhc
·
·
题解
马上就要退休的OIer来水篇题解
这题算法好像不难的说....
考场上比较睿智,想偏了,于是只能拿个暴力分滚粗...
先讲讲暴力的思路(也就是M\le3的分)
由于每种烹饪方法只能用一次,所以菜的数量不会超过N.然后我们对每一种主要食材记录用了几次.于是我们需要M+1维状态,滚动数组可以滚成M维,但是没必要.
然后就可以愉快地DP了.DP方程直接看代码吧,最后把所有合法的状态加起来就是答案了.复杂度为$O(N^{M+1})$,可以拿到64分.(至少没被神仙甩太远2333).
```cpp
#include<bits/stdc++.h>
using namespace std;
#define open(s) freopen( s".in", "r", stdin ), freopen( s".out", "w", stdout )
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[b]); i; v = to[i = nxt[i]] )
template<class T> inline bool cmax( T &x, T y ){ return x < y ? x = y, 1 : 0; }
#define i64 long long
const int mod = 998244353;
int N, M;
int a[105][2005];
namespace brute{
int f[45][45][45][45];
void solve(){
int ans(0);
memset( f, 0, sizeof f );
f[0][0][0][0] = 1;
fp( i, 1, N ) fp( j, 0, i ) fp( k1, 0, j ) fp( k2, 0, j - k1 ){
f[i][j][k1][k2] = ( f[i - 1][j][k1][k2]
+ ( (j && a[i][3]) ? 1ll * f[i - 1][j - 1][k1][k2] * a[i][3] : 0 )
+ ( (k1 && a[i][1]) ? 1ll * f[i - 1][j - 1][k1 - 1][k2] * a[i][1] : 0 )
+ ( (k2 && a[i][2]) ? 1ll * f[i - 1][j - 1][k1][k2 - 1] * a[i][2] : 0 ) ) % mod;
if ( i == N && j && k1 <= (j >> 1) && k2 <= (j >> 1) && (j - k1 - k2) <= (j >> 1) )
ans = ( ans + f[i][j][k1][k2] ) % mod;
}
printf( "%d\n", ans );
}
}
int main(){
open("meal");
scanf( "%d%d", &N, &M );
fp( i, 1, N ) fp( j, 1, M ) scanf( "%d", a[i] + j );
if ( M <= 3 ) return brute::solve(), 0;
return 0;
}
```
接下来讲讲正解.
我们发现同时维护所有主要食材用的次数比较难搞,我们可以想想怎么求不合法的方案数.
由于最多只会有$1$种主要食材用的次数超过了$\lfloor \frac n2 \rfloor$($n$代表菜数),我们可以枚举~~钦定~~哪种主要食材次数超过了$\lfloor \frac n2 \rfloor$.
于是我们可以设计出状态$f[i][j][k]$,当前处理到第$i$种烹饪方法,总共做了$j$道菜,当前钦定不合法的主要食材用了$k$次.最终不合法的状态需要满足$j<2k$.
这样复杂度是$O(N^3M)$的,会TLE.我们可以转换一下思路,$j<2k$就相当于$2k-j>0$,我们只需要记录$j'=2k-j$就可以了.这样就变成了二维$f[i][j']$,总复杂度就变成了$O(N^2M)$,可以跑过.
因为$2k-j$可以是负数,我们需要加上$N$.
代码里面$j$就是$j'$,$k$就是钦定超过$\lfloor \frac n2 \rfloor$的菜.
关于转移方程的解释请参照代码.
```cpp
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define f80 long double
#define rgt register
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline bool cmax( T &x, T y ){ return x < y ? x = y, 1 : 0; }
template<typename T> inline bool cmin( T &x, T y ){ return y < x ? x = y, 1 : 0; }
#define getchar() ( p1 == p2 && ( p1 = bf, p2 = bf + fread( bf, 1, 1 << 21, stdin ), p1 == p2 ) ? EOF : *p1++ )
char bf[1 << 21], *p1(bf), *p2(bf);
template<typename T>
inline void read( T &x ){ char t(getchar()), flg(0); x = 0;
for ( ; !isdigit(t); t = getchar() ) flg = t == '-';
for ( ; isdigit(t); t = getchar() ) x = x * 10 + ( t & 15 );
flg ? x = -x : x;
}
const int mod = 998244353;
int N, M, a[105][2005], s[105];
int f[105][205], ans, t(1);
inline int dec( int x ){ return x >= mod ? x - mod : x; }
signed main(){
read(N), read(M);
fp( i, 1, N ) fp( j, 1, M ) read(a[i][j]), s[i] = dec(s[i] + a[i][j]);
fp( k, 1, M ){
memset( f, 0, sizeof f ), f[0][N] = 1;
fp( i, 1, N ) fp( j, N - i, N + i )
f[i][j] = ( f[i - 1][j] + ( j ? (i64)f[i - 1][j - 1] * a[i][k] : 0 ) + (i64)f[i - 1][j + 1] * (s[i] - a[i][k] + mod) ) % mod; // 需要注意一下j可能是0
//不用i方法/选k食材/不选k食材 然后加起来就OK了.
fp( i, N + 1, N << 1 ) ans = dec(ans + f[N][i]); // 加上所有不合法的方案
}
ans = mod - ans; // 所有方案减去不合法方案就是合法方案数
fp( i, 1, N ) ans = ( ans + (i64)t * s[i] ) % mod, t = ( t + (i64)t * s[i] ) % mod;
printf( "%d\n", (ans + mod) % mod );
return 0;
}
```