Not Too Many Balls-ABC332G
Arrtan_73
·
·
题解
题目大意
给定 n 种球和 m 个盒子，对于第 i 种球有 a_i 个，第 i 个盒子的容量为 b_i，且对于所有满足 1 \le i \le n 且 1 \le j \le m 的整数对 (i, j)，第 j 个球盒子最多放 i \times j 个第 i 种球，求最大的放置数。
### Sol
不难想到网络流算法。
建立源汇点，对于每种球和每一个盒子都新建一个点，源点向球连边，流量为 $a_i$，盒子向汇点连边，流量为 $b_i$，球向盒子连边，流量为 $i \times j$，答案即为最大流。
在此数据范围下，网络流复杂度会炸，由于这个图的结构特殊性，考虑用 $dp$ 模拟网络流。
先将最大流转为最小割，则我们所求即为：
$$
\min (\sum_{i \in X}a_i + \sum_{j \in Y}b_j+\sum_{i \notin X}\sum_{j \notin Y}ij)
$$
我们设 $\sum_{i \notin X}i = k$，则对于所有满足 $\sum_{i \notin X}i = k$ 的集合 $X$ 求出最小的 $\sum_{i \in X}a_i$，显然背包解决即可，则原式化为：
$$
dp_k + k\sum_{j \notin Y}j + \sum_{j \in Y}b_j
$$
对于每一个可能的 $k$，贪心地取 $\min(b_j, jk)$，不难发现将 $b$ 按照 $\lfloor{b_j \over j}\rfloor$ 排序，则取 $b_j$ 和取 $jk$ 的部分为一段前缀和一段后缀，在枚举 $k$ 的过程中同时维护两部分的分界点即可。
由于在递增枚举 $k$ 的过程中，分界点也是单调递增的，最多移动 $m$ 次，保证了复杂度的正确性。
时间复杂度 $O(n ^ 3 + m)$。
### Code
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e2 + 5, M = 5e5 + 5;
int a[N], b[M], dp[N * N], n, m, Ans = 1e18, pos[M];
bool compare(int i, int j){return (int)(b[i] / i) < (int)(b[j] / j);}
signed main(){
cin >> n >> m;
for(int i = 1; i <= n; i++)cin >> a[i];
for(int i = 1; i <= m; i++)cin >> b[i];
memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
for(int i = 1; i <= n; i++)
for(int k = n * (n + 1) / 2; k >= i; k--)
dp[k] = min(dp[k], dp[k - i] + a[i]);//01背包
for(int i = 1; i <= m; i++)pos[i] = i;
sort(pos + 1, pos + m + 1, compare);//按照b[j] / j升序排序
int sum1 = m * (m + 1) / 2, sum2 = 0, loc = 1;
for(int i = 0; i <= n * (n + 1) / 2; i++){
while(i * pos[loc] > b[pos[loc]]){//维护分界点
sum1 -= pos[loc];
sum2 += b[pos[loc]];
loc++;
}
Ans = min(Ans, dp[n * (n + 1) / 2 - i] + i * sum1 + sum2);//维护答案
}
cout << Ans << endl;
return 0;
}
```