ACM - 4743E - 线段树

题目链接

题目理解难度点：
（1）每次改动不恢复，修改的状态保持。
（2）对于一个给定的堆，堆中有i个石子，允许搬运j次。很容易猜想：要平均分配所有的石子，用数学方法可以证明。
当j=2时，7=3+4=5+2=6+1,9+16 < 4+25 < 1+36.
所以，类似贪心，而不是DP，初始化就可以把表格直接打好。
（3）如何维护。线段树。
每次修改第i堆的石子为j，跟搬运次数没有关系，那么就是单点修改，依次pushup修改总方案即可。

剩下的就是线段树模板。代码如下。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long long ull;
typedef long double ld;

const ll MOD = 1e9 + 7;
const int N = 400 + 10;
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 pushup(int rt){
    memset(dp[rt], 0x3f, sizeof(dp[rt]));
    for(int i = 1; i <= m; i++)
        for(int j = 1; j + i <= 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);
    pushup(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);
    pushup(rt);
}

int main(){
    //freopen("input.txt", "r", stdin);
    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]);
    }
    return 0;
}