题号 NC200214
名称 石子搬运
来源 牛客练习赛59
每日一题三期汇总贴~


如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：jxnu19-软技1班-刘晟

Solution

首先我们思考一个简化版的问题，如果不支持修改，我们如何找到搬运完全部石头数的最优解。
考虑动态规划解题，对于一堆石子来说，我们可以枚举搬运次数，根据求解的消耗是很容易发现数学规律，我们要让每次搬运的石头尽可能相同的多，就算有不同的不同的两次之间绝对值差值只能小于等于。
那么我们考虑代表把第堆石子分次搬完的最小花费是多少。这个花费计算也很简单，直接通过先平分，后面多出来的添加个石头把它分完即可。那么我们找到了分别运送每一份石子的最小花费，接下来就是算合并不同堆的操作了，很明显如果干巴巴的转移会发现很难实现，因为合并前个石堆，你并不能记录到你最小的花费之前搬运了几次，如果需要加上的话就要开三维的有点划不来。这里我们考虑用上线段树去优化，前面还是一样的，当我们走到线段树的叶子节点的时候，我们统计代表第堆石子它的最优情况。那么回到它的父亲，就可以对两个儿子之间进行枚举，枚举全部的可能就可以回溯的寻找到答案。注意要初始化成无穷大。

现在我们思考对于每次的修改，他究竟会改变的是什么，他只会改变一个叶子节点，并且之后对线段树路径上和叶子节点在同一边的点才能被更新，那么这里我们就可以使用递归在级的复杂度内完成对新节点的更新。但是回溯的时候依旧是要把全部父亲下面的两个儿子之间进行维护，代码和不修改的几乎一模一样。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

const int N = 400 + 7;
ll n, m, q, x, v;
ll f[N << 2][N], a[N];

#define mid (l+r>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r

ll calc(ll x, int p) { // x个石头分p次运
    int num = x / p;
    int cnt2 = x % p;
    int cnt1 = p - cnt2;
    return 1ll * cnt1 * num * num + 1ll * cnt2 * (num + 1) * (num + 1);
}

void push_up(int rt) {
    ms(f[rt], 0x3f);
    for (int i = 1; i <= m; ++i)
        for (int j = 1; i + j <= m; ++j)
            f[rt][i + j] = min(f[rt][i + j], f[rt << 1][i] + f[rt << 1 | 1][j]);
}

void build(int rt, int l, int r) {
    if (l == r) {
        rep(i, 1, m)
            f[rt][i] = calc(a[l], i);
        return;
    }
    build(lson);
    build(rson);
    push_up(rt);
}

void update(int rt, int l, int r, int pos) {
    if (l == r) {
        rep(i, 1, m)
            f[rt][i] = calc(a[l], i);
        return;
    }
    if (pos <= mid)    update(lson, pos);
    else update(rson, pos);
    push_up(rt);
}

void solve() {
    n = read(), m = read();
    rep(i, 1, n)    a[i] = read();
    build(1, 1, n);
    q = read();
    while (q--) {
        x = read(), v = read();
        a[x] = v;
        update(1, 1, n, x);
        print(f[1][m]);
    }
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目3月17日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴