【每日一题】3月10日石子搬运

题意

有堆石头 牛牛每次都能选择其中一堆然后将其中的石头搬走 如果一次搬运的石子数量是那么这堆石头讲牛牛产生的的负担 然后牛牛最多只能搬次

然后牛能会进行次操作 每一次操作都会改变一堆石子的数量 然后让我们求牛能每一次操作之后 牛牛的最小负担

首先我们不看牛能的操作 很明显对于求牛牛的负担就是一个的过程

因为产生的负担 因此可以知道 如果我们要用次去搬运个石头 那么最好的做法就是将个石头平均分成份 很容易就可以知道吧

如果有不能平分的也很简单 就将多余的每一个组放一个 到放完为止

然后其实后面也就不难了 我们将放在树上 最小面的叶子节点就是直接 然后往上维护的时候就是去枚举子节点的值

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;

const int N = 400 + 7;
const int INF = 0x3f3f3f3f;

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

ll n , m , q , x , v;
ll dp[N << 2][N] , a[N];

ll calc(ll x , int p){
    ll num = x / p ;
    ll cnt1 = x % p ;
    ll cnt2 = p - cnt1;
    return cnt2 * num * num + cnt1 * (num + 1) * (num + 1);
}

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

void build(int rt , int l , int r){
    if(l == r){
        for(int i = 1 ; i <= m ; ++i){
            dp[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){
        for(int i = 1 ; i <= m ; ++i){
            dp[rt][i] = calc(a[l] , i);
        }
        return ;
    }
    if(pos <= mid)  update(lson , pos);
    else update(rson , pos);
    push_up(rt); 
}

void solve(){
    scanf("%lld%lld" , &n , &m);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%lld" , &a[i]);
    build(1 , 1 , n);
    int T;
    scanf("%d" , &T);
    while(T--){
        scanf("%lld%lld" , &x , &v);
        a[x] = v;
        update(1 , 1 , n , x);
        printf("%lld\n" , dp[1][m]);
    }
}

int main(void){
    solve();

    return 0;
}