2020-2021:teams:namespace:codeforces_round_638_div._2

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:namespace:codeforces_round_638_div._2 [2020/07/05 17:53]
great_designer
+++ 2020-2021:teams:namespace:codeforces_round_638_div._2 [2020/07/10 16:29] (当前版本)
great_designer [分析]
@@ 行 596: / 行 596: @@
 输入
-第一行包含两个整数n和k（1\le n，k\le 500）-分别是灌木的数量和篮子容量。
+第一行包含两个整数n和k（$1\le n，k\le 500$）-分别是灌木的数量和篮子容量。
-接下来的n行中的i-th包含两个整数a_i和b_i（$$$0\le a_i，b_i\le 10^9$$）-分别是i-th灌木中红色和蓝色浆果的数量。
+接下来的n行中的i-th包含两个整数a_i和b_i（$0\le a_i，b_i\le 10^9$）-分别是i-th灌木中红色和蓝色浆果的数量。
 输出
@@ 行 656: / 行 656: @@
 在第二个例子中，菲尼克斯可以用第一个（也是唯一一个）灌木的所有浆果填满一个篮子。
-在第三个示例中，Phoenix无法完全填充任何篮子，因为每个灌木中的浆果少于$$$5$$，总红色浆果少于$$$5$$，总蓝色浆果少于$$$5$$。
+在第三个示例中，Phoenix无法完全填充任何篮子，因为每个灌木中的浆果少于5，总红色浆果少于5，总蓝色浆果少于5。
 在第四个例子中，菲尼克斯可以把所有的红色浆果放进篮子里，留下一个额外的蓝色浆果。
 ====分析====
-（暂无思路）
 大致意思是只能从矩阵同行或同列取值，要求每次取值必须填满篮子（k个），问最多填多少个篮子。
+$n$棵树每棵树上$a_i$个红果，$b_i$个蓝果，每个篮子容量为$k$，可以装同一棵树上的果实（条件一）或者颜色相同的果实（条件二），问最多使多少篮子恰好填满
+$1 \le n,k \le 500,1\le a_i,b_i\le 1e9$
+以下搬运自其他页面的本题题解：
+考虑暴力$dp$, $dp[i][j][k]$表示考虑到第$i$种物品，红色的篮子还可以放$j$个，蓝色的篮子还可以放$k$个的最大值。
+这样如果直接的转移是$n^5$的，显然不行。可以考虑一下$j$是否能推出$k$。
+发现有$果实总数-dp[i][j]*每框个数=k$
+转移就是枚举之前红色的框剩几个，现在红色的框剩几个。剩下的差就是本次与蓝色单独装框的即可。
+考虑到对于一棵树如果装在$t$个篮子中，一定可以使大于等于$t-1$个篮子满足条件一，因而所有最优解中存在一种方案使得每棵树最多提供一个满足条件二的篮子
+因而记$f(i,j)$表示前$i$棵树装完剩余$j$个红果的最大篮子数,$S_i$表示前$i$棵树果子总和,可以推得剩余蓝果数量为$S_i-f(i,j)*k-j$
+下面只简述存在条件二篮子的转移
+枚举该篮子中红果数量$num_1$，蓝果为$k-num_1$；令$t_1=j-num_1+a_i,t_2=S_i-f(i,j)*k-j-k+num_1+b_i$
+转移方程$f(i+1,t_1\%k)=max(f(i+1,t_1\%k),f(i,j)+1+t_1/k+t_2/k)$
 =====F=====

2020-2021/teams/namespace/codeforces_round_638_div._2.1593942786.txt.gz · 最后更改: 2020/07/05 17:53 由 great_designer