网站开发会用到定时器功能,夫唯seo系统培训,怎么做一个小程序,厦门小程序开发的公司NOIP2019 Emiya家今天的饭
ACM退役选手远程口胡 csf如今真的是太菜了,最后16分的做法愣是想了一下午 考虑使用容斥方法:
1
采用动态规划,先求出在无限制情况下,安排kkk种烹饪方法总的方案数. 记dp2[i][j]dp2[i][j]dp2[i][j]表示已经考虑完前iii种烹饪方法,共做了jjj个菜的方…NOIP2019 Emiya家今天的饭
ACM退役选手远程口胡 csf如今真的是太菜了,最后16分的做法愣是想了一下午 考虑使用容斥方法:
1
采用动态规划,先求出在无限制情况下,安排kkk种烹饪方法总的方案数. 记dp2[i][j]dp2[i][j]dp2[i][j]表示已经考虑完前iii种烹饪方法,共做了jjj个菜的方案数. 那么显然,决策分2种情况,用或不用第iii种烹饪方法,用的话就只能选一种主要食材. dp2[i][j]dp2[i−1][j]dp2[i−1][j−1]∗(∑t1ma[i][t])dp2[i][j]dp2[i-1][j] dp2[i-1][j-1]*(\sum_{t1}^m a[i][t])dp2[i][j]dp2[i−1][j]dp2[i−1][j−1]∗(∑t1ma[i][t]) 时间复杂度O(n2)O(n^2)O(n2),∑t1ma[i][t]\sum_{t1}^m a[i][t]∑t1ma[i][t]可以提前维护好.
2
采用动态规划,计算出那些不合法的方案,并将这些方案减掉. 因为每次只能有一个主要食材不合法.所以对每个主要食材单独考虑,假设当前ttt食材不合法了. 最朴素的想法是,采用dp1[i][j][k]dp1[i][j][k]dp1[i][j][k]表示考虑完前iii种烹饪方法,已经做了jjj个菜,使用ttt食材的有kkk个的方案数.
那么,决策就是第iii中烹饪方案选不选,选了之后,选不选ttt作为食材,一共333个转移.
记录linesum[i]∑t1ma[i][t]linesum[i]\sum_{t1}^m a[i][t]linesum[i]∑t1ma[i][t]
dp1[i][j][k]dp1[i−1][j][k]dp1[i−1][j−1][k−1]∗a[i][t]dp1[i−1][j−1][k]∗(linesum[i]−a[i][t])dp1[i][j][k]dp1[i-1][j][k]dp1[i-1][j-1][k-1]*a[i][t]dp1[i-1][j-1][k]*(linesum[i]-a[i][t])dp1[i][j][k]dp1[i−1][j][k]dp1[i−1][j−1][k−1]∗a[i][t]dp1[i−1][j−1][k]∗(linesum[i]−a[i][t])
最后答案减去dp1[n][j][k]∣kj/2dp1[n][j][k]|_{k \gt j/2}dp1[n][j][k]∣kj/2
时间复杂度为O(n3m)O(n^3m)O(n3m),只能过84分,接下来继续优化
事实上,我们无需同时记录jjj和kkk,而只需要记录k−(j−k)k - (j-k)k−(j−k)的值就足够了,也就是ttt食材的数量和非ttt食材的数量.
这样的话,记录dp1[i][Δ]dp1[i][\Delta]dp1[i][Δ]表示考虑完前iii行,选取的ttt食材和非ttt食材的差值为Δ\DeltaΔ时候,方案数. 转移方程如下 dp1[i][Δ]dp1[i−1][Δ]dp1[i−1][Δ−1]∗a[i][t]dp1[i−1][Δ1]∗(linesum[i]−a[i][t])dp1[i][\Delta]dp1[i-1][\Delta] dp1[i-1][\Delta-1]*a[i][t]dp1[i-1][\Delta1]*(linesum[i]-a[i][t])dp1[i][Δ]dp1[i−1][Δ]dp1[i−1][Δ−1]∗a[i][t]dp1[i−1][Δ1]∗(linesum[i]−a[i][t]) 最后答案减去dp1[n][Δ]∣Δ0dp1[n][\Delta]|_{\Delta0}dp1[n][Δ]∣Δ0 时间复杂度O(n2m)O(n^2m)O(n2m)
综上,总的时间复杂度O(n2m)O(n^2m)O(n2m)
AC代码
#include iostream
#include cstring
using namespace std;
#define int long long
const int MOD 998244353;
const int maxn 107,maxm 2007;
int dp1[maxn][2*maxn]; //
int dp2[maxn][maxn];
int linesum[maxn]; //s1表示
int a[maxn][maxm];
int n, m;
signed main() {cin n m;for(int i 1;i n;i) {for(int j 1;j m;j) {cin a[i][j];a[i][j] % MOD;linesum[i] ( linesum[i] a[i][j] ) % MOD;}}int ans 0;for(int t 1;t m;t) {memset(dp1,0,sizeof(dp1));dp1[0][0 100] 1;for(int i 1;i n;i) {for(int j -i 100;j i 100;j) {dp1[i][j] dp1[i-1][j];dp1[i][j] (dp1[i-1][j-1] * a[i][t]) % MOD;//取dp1[i][j] (dp1[i-1][j1] * ((linesum[i] - a[i][t] MOD) % MOD)) % MOD;//不取dp1[i][j] % MOD;}}for(int j 1;j n;j) {ans (ans - dp1[n][j 100]) % MOD;}}dp2[0][0] 1;for(int i 1;i n;i) {for(int j 0;j i;j) {dp2[i][j] dp2[i-1][j];for(int k 1;k m;k) {dp2[i][j] dp2[i-1][j-1] * a[i][k] % MOD;dp2[i][j] % MOD;}}}for(int j 1;j n;j)ans (ans dp2[n][j]) % MOD;cout ans endl;return 0;
}
