[ABC332G] Not Too Many Balls

· · 题解

一道综合性非常强的好题。

首先，本题的基本模型是一个非常裸的最大流：

原点向颜色 i 连容量 a_i 的边；

颜色 i 向盒子 j 连容量 i\cdot j 的边；

盒子 j 向汇点连容量 b_j 的边。

但暴力连边并跑最大流会超时。

考虑到无法优化建边，将最大流转化为最小割，尝试解决。

记集合 A=[1,n],B=[1,m]，如果割掉 (s,i) 边，记 i 在集合 S 中；割掉 (j,t) 边，记 j 在集合 T 中。最小割就是：

\min(\sum_{i\in S}a_i+\sum_{i\in A-S,j\in B-T}i\cdot j+\sum_{j\in T}b_j)

中间一项的意思是，如果 (i,j) 边左连原点，右连汇点，就需要割断。

看到 n 很小，考虑枚举 k，感性理解为左边不割的下标和。记：

k=\sum_{i\in A-S}i

原式改写为：

\min(\sum_{i\in S}a_i+\sum_{j\in B-T}k\cdot j+\sum_{j\in T}b_j)

再想一下，右边两项可以理解为，对每个 j 可以自由地选择割掉容量为 b_j 的边或容量为 k\cdot j 的边。

\min(\sum_{i\in S}a_i+\sum_{j\in B}\min(k\cdot j,b_j))

外层枚举着 k，贪心地对每个 j 自由选择，至于左边那一项，可以预处理 DP。

DP 的具体思路：

记 f(i,j) 表示到下标 i 为止，选择了若干 i' 不割掉 (s,i') 边，\sum i'=j（j 其实就是上文提到的 k），最小割。

转移有：割 (s,i)，f(i,j)=f(i-1,j)+a_i；不割，f(i,j)=f(i-1,j-i)。

贪心的具体思路：

对每一个 j 预处理 b_j\le j\cdot k 的最小 k，也就是到达这个 k 就开始选择 b_j。移项得 k\ge b_j/j，k 的最小整数值即为 b_j/j 上取整。按这个值排序。

一开始假设每个 j 都选 j\cdot k。随着 k 的增长，j\cdot k 会逐步被 b_j 替代掉，按照先前制定的顺序依次修改即可。

// Title:  Not Too Many Balls
// Source: ABC332G
// Author: Jerrywang
#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<ll, int>
#define ll long long
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
const int N=505, M=500010;
using namespace std;
inline ll read()
{
    ll x=0, f=1;
    char c=getchar();
    while(!isdigit(c)) {if(c=='-') f=-1; c=getchar();}
    while(isdigit(c)) {x=(x<<3)+(x<<1)+c-'0'; c=getchar();}
    return x*f;
}

int n, m; ll a[N], b[M]; pii t[M];
ll f[N][N*N]; // a数组到i为止，不割掉的下标和为j，最小总和
int main()
{
    #ifdef Jerrywang
    freopen("in.txt", "r", stdin);
    #endif
    n=read(), m=read();
    rep(i, 1, n) a[i]=read();
    rep(i, 1, m) b[i]=read();
    rep(i, 1, n) rep(j, 0, n*n)
    {
        f[i][j]=f[i-1][j]+a[i];
        if(j>=i) f[i][j]=min(f[i][j], f[i-1][j-i]);
    }
    rep(i, 1, m) t[i]={(b[i]+i-1)/i, i}; // b[j]<=jk的最小k
    sort(t+1, t+m+1);
    int i=1;
    ll sum1=(ll)m*(m+1)/2, sum2=0, ans=LLONG_MAX;
    rep(k, 0, n*n)
    {
        while(i<=m && t[i].F==k)
        {
            sum1-=t[i].S; sum2+=b[t[i].S];
            i++;
        }
        ans=min(ans, f[n][k]+k*sum1+sum2);
    }
    printf("%lld", ans);

    return 0;
}