思路

我线段树属于那种看到题解一般能懂,自己有时候想不到的层次...
这题应该就是一个线段树...
单纯的已知次数下搬运石头肯定是平方答案最优.然后假如不含修改的话,就是一个超级简单的.
假如含有修改呢...我们不妨把它放到线段树上进行.
令表示为到了这个石头堆(因为线段树是一群一群石头进行维护的嘛~)选了次的最小代价是多少.然后我们愉快的维护这个数组就好了...

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e2+5;
int n,m,q;
ll a[N],f[N<<2][N];
struct Tree{
    int l,r,len;
}tr[N<<2];
ll cost(int n,int m)//n个石子分m次搬运的最小花费.
{
    int num=n/m;
    return 1ll*(m-n%m)*num*num+1ll*(n%m)*(num+1)*(num+1);
}

void pushup(int u)
{
    memset(f[u],0x3f3f3f3f,sizeof f[u]);
    if(tr[u].len==1)
    {
        for(int i=1;i<=m-n+1;i++)
        {
            if(i>=a[tr[u].l]) f[u][i]=a[tr[u].l];
            else
            {
                f[u][i]=cost(a[tr[u].l],i);
            }
        }
        return;
    }
    for(int j=tr[u].len;j<=m-n+tr[u].len;j++)
    {
        for(int k=tr[u<<1].len;k<=j-tr[u<<1|1].len;k++)
        {
            f[u][j]=min(f[u][j],f[u<<1][k]+f[u<<1|1][j-k]);
        }
    }
}

void modify(int u,int pos)
{
    if(tr[u].len==1)
    {
        pushup(u);
        return;
    }
    if(tr[u<<1].r>=pos)
    {
        modify(u<<1,pos);
        pushup(u);
    }
    else
    {
        modify(u<<1|1,pos);
        pushup(u);
    }
}

void build(int u,int l,int r)
{
    tr[u].l=l,tr[u].r=r,tr[u].len=(r-l+1);
    if(l==r)
    {
        for(int i=1;i<=m-n+1;i++)
        {
            if(i>=a[l]) f[u][i]=a[l];
            else
            {
                f[u][i]=cost(a[l],i);
            }
        }
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)   scanf("%lld",&a[i]);
    build(1,1,n);
    scanf("%d",&q);
    while(q--)
    {
        int x,v;
        scanf("%d%d",&x,&v);
        a[x]=v;
        modify(1,x);
        printf("%lld\n",f[1][m]);
    }
    return 0;
}