[USACO07NOV]电话线Telephone Wire

Luogu P2885

思路

设第$i$根树高$j$时,前$i$棵树的花费为$f[i][j]$,则易得dp方程

$$f[i][j]=\min \limits_{h[i-1]\leq k\leq 100}\{f[i-1][k]+|j-k|\cdot C+(j-h_{i})^2\}$$

化简得

$$f[i][j]=\min \limits_{h[i-1]\leq k\leq 100}\{f[i-1][k]- k\cdot C\}+j\cdot C+j^2+h_{i}^{2}-2\cdot j\cdot h_{i}(j\geq k)$$

$$f[i][j]=\min \limits_{h[i-1]\leq k\leq 100}\{f[i-1][k]+k\cdot C\}-j\cdot C+j^2+h_{i}^{2}-2\cdot j\cdot h_{i}(j\leq k)$$

对于前一个式子正着DP一下,后一个倒着DP一下即可

$O(100\cdot N)$

代码

#include <iostream>
#include <cstdio>

long long abs(long long x){return x>=0 ? x : -x;}

int N, C, h[100010], mx;
long long f[100010][110];

int main(){
    scanf("%d%d", &N, &C);
    for(int i=1; i<=N; i++){
        scanf("%d", &h[i]);
        mx=std::max(mx, h[i]);
    }
    for(int i=1; i<=N; i++)	std::fill(f[i]+h[i], f[i]+mx+1, 0x3f3f3f3f);
    for(int i=1; i<=100; i++)	f[1][i]=1LL*(i-h[1])*(i-h[1]);
    for(int i=2; i<=N; i++){
        long long mn=0x3f3f3f3f;
        for(int j=mx; j>=h[i]; j--){
            if(j>=h[i-1])	mn=std::min(mn, f[i-1][j]+1LL*j*C);
            f[i][j]=std::min(f[i][j], (long long)mn-j*C+j*j+h[i]*h[i]-2*j*h[i]);
        }
        mn=0x3f3f3f3f;
        for(int j=std::min(h[i], h[i-1]); j<=mx; j++){
            if(j>=h[i-1])mn=std::min(mn, f[i-1][j]-1LL*j*C);
            f[i][j]=std::min(f[i][j], (long long)mn+j*C+j*j+h[i]*h[i]-2*j*h[i]);
        }
    }
    long long ans=0x3f3f3f3f3f3f3f3f;
    for(int i=h[N]; i<=mx; i++)
        ans=std::min(ans, f[N][i]);
    printf("%lld", ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注