首页 > 其他分享 >Emiya今天的饭 题解

Emiya今天的饭 题解

时间:2023-12-07 21:34:13浏览次数:30  
标签:烹饪 方式 题解 sum times 今天 Emiya 食材

题目

考虑条件主要食材最大的不超过总菜数的一半,不好处理,但存在主要食材最大的超过总菜数的一半是好处理的,容斥即可。

首先计算所有情况,由于题目要求每个烹饪方式最多使用一次,很明显可以记 \(g_i\) 表示前 \(i\) 种烹饪方式的方案数。

\[g_i = g_{i-1}+g_{i-1} \times \sum_{j=1}^{m}a_{i,j} \]

预处理 \(sum_i = \sum_{j=1}^{m} a_{i,j}\),计算 \(g_n\) 是 \(O(n)\) 的,得到 \(g_n-1\) 即为所有情况。

接下来考虑不合法的情况,首先钦定食材 \(x\) 超过一半,即食材 \(x\) 用的次数比其他菜的数量加起来都多。

显然记 \(f_{i,j,k}\) 表示前 \(i\) 种烹饪方式,食材 \(x\) 做了 \(j\) 道菜,其他食材做了 \(k\) 道菜,转移有三种情况。

  • 不选这种烹饪方式,\(f_{i-1,j,k}\)。
  • 用这种烹饪方式做食材 \(x\),\(f_{i-1,j-1,k} \times a_{i,x}\)。
  • 用这种烹饪方式做其他食材,\(f_{i-1,j,k-1} \times \sum_{l=1}^{m(l \ne x)}a_{i,l}\)。

转移即为:

\[f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k} \times a_{i,x}+f_{i-1,j,k-1} \times (sum_i-a_{i,x}) \]

不合法的情况为

\[\sum_{j>k} f_{n,j,k} \]

这样计算,状态是 \(O(n^3)\) 的,转移是 \(O(1)\) 的,枚举 \(x\) 是 \(O(m)\),总时间复杂度为 \(O(n^3m)\)。

考虑优化状态,最后只用统计 \(j>k\),因此只需要记录 \(j-k\) 即可,这样状态变成了 \(f_{i,j}\)。

转移只需要改一点:

\[f_{i,j}=f_{i-1,j}+f_{i-1,j-1} \times a_{i,x}+f_{i-1,j+1} \times (sum_i-a_{i,x}) \]

总时间复杂度 \(O(n^2m)\)。

标签:烹饪,方式,题解,sum,times,今天,Emiya,食材
From: https://www.cnblogs.com/xcs123/p/17884022.html

相关文章

  • 虚拟机运行Hadoop | 各种问题解决的心路历程
    ps:完成大数据技术实验报告的过程,出项各种稀奇古怪的问题。(知道这叫什么吗?经济基础决定上层建筑,我当时配置可能留下了一堆隐患,总之如果有同样的问题,希望可以帮到你)一、虚拟机网络连接不通的各种情况我这里遇到的是,三台虚拟机,两台piing百度不同原因:改了下内存,重启就又未知的网......
  • 【luogu题解】U388218 数数
    数数题目描述给定n个不超过1.5×10⁹的自然数。求这些自然数各自出现的次数,并按照自然数从小到大的顺序输出统计结果。输入格式输入的第1行是整数n,表示自然数的个数。第2行到第n+1行每行一个自然数。输出格式输出文件包含m行(m为n个自然数中不相同数的个......
  • [ARC121F] Logical Operations on Tree 题解
    题目链接点击打开链接题目解法比较好的题首先要发现一个性质是:先删AND边,再删OR边最优小证一下:分类讨论AND边两端的数字情况\(0\&0\)左右两端虽然可能可以把\(1\)OR过来,但这种情况先做\(\&\),也一定可以OR得到\(1\)\(0\&1\)左边可能可以\(OR\)得到\(1......
  • T403510 平面划分(Hard) 题解
    LinkT403510平面划分(Hard)Question平面上由\(n\)条这样的折线所界定区域的最大的个数\(Z_n\)是多少。Solution先思考一个简单的问题平面上\(n\)条直线所界定的区域最大个数\(L_n\)是多少?我们考虑假设已经有\(n-1\)条直线,我们需要画一条直线,这条直线最多和\(n......
  • 【题解】CodeForces 1902F Trees and XOR Queries Again
    传送门:https://codeforces.com/contest/1902/problem/F数据结构题,这里讲两种思路。$ST$表思路:判定“从若干个数中能否取出其中一些,使得异或和为$x$”的问题,第一时间想到线性基,本题要做的显然就是快速求出询问路径上所有数的线性基。两组数的线性基可以合并,方法为“暴力将......
  • [ARC106E] Medals 题解
    题目链接题目链接题目解法感觉不难啊,怎么想到网络流和\(hall\)定理后面就屁都没想到呢首先一眼网络流先二分答案考虑一个朴素的建图方法是:把每个人拆成\(k\)个点,然后往在的天连边,跑最大流,满流即合法可以发现,跑网络流对这道题还说没有必要,因为只要判是否有完美匹配不难......
  • 【UVA 101】The Blocks Problem 题解(模拟+向量)
    计算机科学的许多领域使用简单、抽象的领域进行分析和实证研究。例如,早期的人工智能规划和机器人研究(STRIPS)使用了一个区块世界,其中机器人arm执行涉及块操作的任务。在这个问题中,您将在某些规则和约束下对一个简单的块世界进行建模。相当地与确定如何达到指定状态相比,您将“编程......
  • Maven无法下载fastdfs-client-java依赖问题解决
    一、分析原因控制台报错具体如下:并且pom.xml中以下依赖爆红:<dependency><groupId>org.csource</groupId><artifactId>fastdfs-client-java</artifactId><version>1.29-SNAPSHOT</version></dependency>原因:因为fastdfs-clien......
  • [CF83E] Two Subsequences 题解
    [CF83E]TwoSubsequences题解思路定义\(overlap(a,b)\)为字符串\(a\)的后缀与\(b\)的前缀的最大相等的长度,有\(|f(a,b)|=|a|+|b|-overlap(a,b)\),下文称匹配为相邻两串的\(overlap\)。观察到每次操作之后,一定有一个序列是以\(a_i\)为结尾的。所以根据这个......
  • CF1900B题解
    原题思路略微思考不难得到,三个数字的数量之差的奇偶性是不会变的。因为一个数的数量减少了$1$,另一个数无论是增加$1$或是减少$1$,两者的差要么不变,要么增加/减少$2$,对奇偶性无影响。同时,如果另外两个数的数量变为$0$,它们数目的差一定是$0$。那么,我们只需要判断另外两个......