题目链接：https://ac.nowcoder.com/acm/problem/200214

描述

有n堆石子，第1，2，3...i堆分别为a1，a2，a3...ai个，能通过m次搬运来搬运所有石子，同时只能搬运其中一堆的一些石子，每次搬运会产生搬运石子数量平方的负担，q次询问x v会将第x堆石子变成v个，每次询问完输出最小负担。

思路

如何去操作呢？
\\\\\\\题目数据范围并不是很大，可以在线段树上动态规划去维护这样一个dp数组，第一维代表树的结点，表示区间上通过i次搬运的最优解，每次递归到某个结点时时从1到m去枚举所有可能的次数，通过左儿子和右儿子相加取最小值来更新dp数组 注意每次更新都要将结点上的数初始化为无穷。
最后的dp[1][m]就代表线段树结点1在搬运次数m下的解，也就是整个区间的最优解

    mem(dp[node],0x3f);
    for(int i=1;i<=m;i++){
        for(int j=1;j+i<=m;j++){
            dp[node][i+j]=min(dp[l_node][i]+dp[r_node][j],dp[node][i+j]);
        }
    }

那么如何求一堆a个石子，通过m次搬运的最小负担呢？
我们可以发现将a个石子均分成m次搬，多了几份就在多少份上加1 ，这种情况下的负担最小，我们很容易就能求出它
eg：17个石子，5次搬运
3 3 3 3 3 多了两个->3 3 3 4 4;

#include <bits/stdc++.h>

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define mem(a, b) memset(a, b, sizeof(a))
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
const long long N = 1e6 + 7;
const double eps = 1e-6;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const long long mod = 1e9 + 7;
const int dir[][2] = {{0, 1}, {1, 0},  {0, -1}, {-1, 0},
                      {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const ll inf_ll = 0x3f3f3f3f3f3f3f3f;
#define mid (l+r>>1)
#define l_node node*2
#define r_node node*2+1
int m,n,k;
int a[407];
int dp[1628][407];
void add_up(int node){
    mem(dp[node],0x3f);
    for(int i=1;i<=m;i++){
        for(int j=1;j+i<=m;j++){
            dp[node][i+j]=min(dp[l_node][i]+dp[r_node][j],dp[node][i+j]);
        }
    }
}
int cal(int a,int n){//a个 搬n次花费最小；
     return (n-a%n)*(a/n)*(a/n)+((a/n)+1)*((a/n)+1)*(a%n);
}
void updata(int node,int l,int r,int num){
    if(l==r){
        for(int i=1;i<=m;i++){
            dp[node][i]=cal(a[l],i);
        }
        return ;
    }
    if(num<=mid)updata(l_node,l,mid,num);
    else updata(r_node,mid+1,r,num);
    add_up(node);
}
void build(int node,int l,int r){
    if(l==r){
        for(int i=1;i<=m;i++){
            dp[node][i]=cal(a[l],i);
        }
        return ;
    }
    build(l_node,l,mid);
    build(r_node,mid+1,r);
    add_up(node);
}
signed main() {
    ios;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    cin>>k;
    while(k--){
         int pl,num;cin>>pl>>num;
         a[pl]=num;
         updata(1,1,n,pl);
         cout<<dp[1][m]<<endl;
    }
}