牛客练习赛59——E石子搬运

网址：https://ac.nowcoder.com/acm/contest/4743/E

题目描述

有{n堆石子，第i堆石子的石子数量是ai，作为牛客网的一头领头牛，牛牛决定把这些石子搬回牛客。如果牛牛一次搬运的石子数量是k，那么这堆石子将对牛牛产生k^2的负担值。牛牛最多只能搬运m次，每次搬运可以从一堆石子中选出一些石子搬回牛客，每次搬运不能同时从两堆石子中选取石子，每次只能搬运整数个石子。牛牛是一只聪明的牛，他想出了一种搬运计划可以最小化他搬运完这些石子的负担值的总和，但是突然牛牛的死敌牛能出现了，牛能每次可以施展以下的魔法：x,v将第x堆石子的数量变为v这打乱了牛牛的计划，每次牛能施展一次魔法，牛牛就得重新规划他的搬运方案，但是牛能施展魔法的次数太多了，牛牛根本忙活不过来了，于是他请来了聪明的你帮他写一个程序计算。

输入描述:

第一行两个整数n,m
第二行n个整数a 1,a2...a n
第三行一个整数q，表示牛能施展魔法的次数
接下来q行每行两个整数 x v，表示牛能将第x堆石子的数量变为了v

输出描述:

输出包含q行，每行输出一个整数表示在牛能施展魔法后，牛牛搬完所有n堆石子所产生最小化的负担值的总和。

输入

3 4
2 2 2
3
1 2
1 3
2 6

输出

10
13
31

备注:

1<=n<=m<=400,1<=x<=n,1<=q<=400,1<=ai,v<=1e5

题解：

这道题对于现在的我来说比较难。
在这里引用小乔(☆_☆)的题解https://ac.nowcoder.com/discuss/381692
首先，让我们看看问题不修改的话我们怎么做。
设dp[i][j]表示第i堆石子搬运j次需要的最小代价。对于单堆石子，最优的策略是把ai个石子均分在j次搬运上。可以证明这是最优的策略：
假设这样产生的花费为sum，而每次搬运的个数都为x，我们把某次搬运的个数−1，加到另一次搬运上，重新计算的花费为sum−(x∗x−(x−1)∗(x−1))+((x+1)∗(x+1)−x∗x)，对于任意x>0，一定有(x+1)(x+1)-xx>xx-(x-1)(x-1)，那么花费增加了。
再考虑两堆石子x,y，我们知道dp[x][k1]和dp[y][k2]，另dp[z][j]表示两堆搬运j次全部搬完的代价，有dp[z][k1+k2]=min(dp[x][k1]+dp[y][k2])。
如果没有修改，我们从前往后遍历进行dp得出答案，这样单次处理的时间复杂度为O(n^3)。如果处理q次，因为n,q同阶，时间复杂度为O(n^4)，但复杂度太高会得到TLE。
注意到本题每次仅修改一个点，那么是否可以把dp稍做修改，使得每次修改后可以快速得出答案呢？这显然是可以的，考虑4堆石子x1,x2,x3,x4，我们先合并x1,x2的答案，再合并x3,x4的答案，再将x1,x2和x3,x4的答案合并，这不影响最终的结果。
这样，我们可以采用分治的思想来进行dp（类似于线段树），因为最多4*n个结点，所以初始化的时间复杂度为n^3，但对于后面的每次修改，就相当于线段树单点修改，单点修改的时间复杂度为n^2lognlogn，总的时间复杂度O(n^3logn)，发现这样复杂度其实也挺大的，但别忘了还有一个小技巧size优化，利用size优化后时间跑不满，足以通过这道题。

AC题解：

 #include<iostream>
#include<cstring>
using namespace std;
#define ll long long int
//表示无穷大，是10^9级别的，而且可以使用memset(a,inf,sizeof(a); 
#define inf 0x3f3f3f3f
const int maxn=410;
ll dp[4*maxn][maxn];//dp[u][i]代表结点u所包括的所有堆石子一共搬运i次搬完所需要的最小负担值 
ll a[maxn];
int len[4*maxn];//计算每个结点所包含的数组a中的元素的个数 
int n,m,q;
int node[4*maxn][2];//结点的左右孩子 
void Update(int u){//计算节点u的dp值 
    memset(dp[u],inf,sizeof(dp[u]));//初始化
    //分为对叶子节点的计算和对非叶子节点的计算 
    if(len[u]==1){
        int now=node[u][0];
        for(int i=1;i<=m-n+1;i++){
            if(i>=a[now]) dp[u][i]=a[now];
            else {
                ll ev=a[now]/i;
                dp[u][i]=(a[now]%i)*(ev+1)*(ev+1)+(i-a[now]%i)*ev*ev;
            }
        }
        return ;
    }
    int l=u*2,r=u*2+1;
    for(int i=len[u];i<=m-n+len[u];i++){
        for(int j=len[l];j<=i-len[r];j++){
            dp[u][i]=min(dp[u][i],dp[l][j]+dp[r][i-j]);//两堆石子等于遍历每一组石子之和的最小值 
        }
    }
}
void BuildTree(int l,int r,int u){//递归创建 
    len[u]=r-l+1; 
    node[u][0]=l,node[u][1]=r;
    if(l==r){//先计算出叶子节点的dp值 
        for(int i=1;i<=m-n+1;i++){
            if(i>=a[l]) dp[u][i]=a[l];//这种情况下肯定每次都运1 
            else {
                ll ev=a[l]/i;
                dp[u][i]=(a[l]%i)*(ev+1)*(ev+1)+(i-a[l]%i)*ev*ev;//这里需要注意，之前写的不合格
                /*
                ll ev=a[l]/i;
                ll sh=a[l]-a[l]/i;
                dp[u][i]=ev*ev*(i-1)+sh*sh;
                */
            }
        }
        return ;
    }
    BuildTree(l,(l+r)/2,u*2);
    BuildTree((l+r)/2+1,r,u*2+1);
    Update(u);//当所有结点都创建完之后，便开始回归地计算每个节点的dp值 
}
void Modify(int x,int u){
    if(len[u]==1) {
        Update(u);
        return ;
    }
    if(x<=node[u*2][1]) {
        Modify(x,u*2);
        Update(u);
    }
    else {
        Modify(x,u*2+1);
        Update(u);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>q;
    BuildTree(1,n,1);//创建线段树 
    while(q--){
        ll x,v;
        cin>>x>>v;
        a[x]=v;
        Modify(x,1);//修改新输入的一个结点，及其与根结点路径上的所有结点 
        cout<<dp[1][m]<<endl;
    }
    return 0;
}

注：理解题解外加写代码基本上花费将近四个小时，幸好今天的周休。AC之后收获了慢慢的满足感。

打卡第5天！！！让未来的自己感谢现在努力的自己。