题意

n个果园运到2个基地中，要求全部果子都运完，用时为所有路的用时中最大值t1，要求所有运了果子的果园的c之和<=b。

2个基地将会处理所有果子，对于i号果园运到j号基地的w个果子，用时为w*u(u的定义见输入)，这部分用时为所有用时的最大值t2。

求min(t2+t1)。

20pts

暴力搜索即可（当然也可以背包）

40pts

简单优化一下背包即可

60pts

这里加上$c_{i,j}=1c\_\{i,j\}=1$ci,j​=1的限制的部分分

考虑对距离加个上限再背包即可

100pts

现在考虑4维 可能也可以理解为5维 的背包

但是好像跑得挺快的

时间复杂度应该是$O\left(n{\sum }_{i=1}^{n-1}{a}_i{a}_{i+1}{b}^2\right)O(n\backslash sum\_\{i=1\}^\{n-1\}\; a\_ia\_\{i+1\}b^2)$O(n∑i=1n−1​ai​ai+1​b2)

因为$n={\sum }_{i=1}^n{a}_{i}n=\backslash sum\_\{i=1\}^\{n\}\; a\_i$n=∑i=1n​ai​，所以这玩意在随机数据下应该挺快的

同时我们可以把不生产果子的果园打个不使用的tag，在dp转移时跳过该果园。

当然可以直接删掉，下面写的方程就是这样的

设$f_{i,j,k,l,1/0}f\_\{i,j,k,l,1/0\}$fi,j,k,l,1/0​表示已考虑前i个果园，其中第i个果园向一号基地运j吨果子，现在1号基地已开k台机器，2号则开l台机器的最优方案，最后一维为0表示最优方案的运输部分用时，为1表示最优方案的加工部分用时。

现在枚举i,j,k,l，把当前状态转移到前i+1个果园的状态，所以再枚举一个j2表示i+1号果园运j2吨果子去1号基地。

接下来上方程：

fi,j,k,l​⇒⎩⎪⎨⎪⎧​fi+1,j2,k,l+c2,i+1​​fi+1,j2,k+c1,i+1​,l​fi+1,j2,k+c1,i+1​,l+c2,i+1​​​j2==0j2==ai+1​else​

当然上述方程是建立在转移后更优的情况下的。

最后的答案统计非常简单，把$f_{n,j,k,l}f\_\{n,j,k,l\}$fn,j,k,l​扫一遍就行

code