1705. [Usaco2007 Nov]Telephone Wire 架设电话线

显然 $dp$，首先设 $f[i][j]$ 表示当前考虑到第 $i$ 个电线杆，高度为 $j$ 时的最小代价

那么有转移 $f[i][j]=f[i-1][k]+cost+C(j-k)$，其中 $j>=k$，$cost$ 为把电线杆 $i$ 增高到 $j$ 的代价，$i,j$ 固定时为常数

对于 $i,j$ 的最优转移 $k'$，$i,j+1$ 时小于 $j$ 的所有转移代价同时增加 $C$，所有对于 $k<j$ 的位置只有 $k'$ 有机会贡献

当 $k>j$ 时也同理，动态维护即可

其实直接维护前缀 $f[i][j]-Ck$ 最小值会好写很多...

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=1e5+,M=;

const ll INF=1e18;

int n,C,h[N],H;

ll f[][M],ans=INF;

inline ll calc(int i,int j,int k) { return f[(i&)^][k]+(j-h[i])*(j-h[i])+C*abs(j-k); }

int main()

{

    n=read(),C=read();

    for(int i=;i<=n;i++) h[i]=read(),H=max(H,h[i]);

    for(int i=h[];i<=H;i++) f[][i]=(i-h[])*(i-h[]);

    for(int i=;i<=n;i++)

    {

        int pre=h[i-],p=i&;

        for(int j=;j<=H;j++) f[p][j]=INF;

        for(int k=pre+;k<h[i];k++) if(calc(i,h[i],pre)>calc(i,h[i],k)) pre=k;

        for(int j=max(h[i],h[i-]);j<=H;j++)

        {

            if(calc(i,j,pre)>calc(i,j,j)) pre=j;

            f[p][j]=calc(i,j,pre);

        }

        pre=H;

        for(int j=H-;j>=h[i];j--)

        {

            if(j+>=h[i-] && calc(i,j,pre)>calc(i,j,j+)) pre=j+;

            f[p][j]=min(f[p][j],calc(i,j,pre));

        }

    }

    for(int i=h[n];i<=H;i++) ans=min(ans,f[n&][i]);

    printf("%lld\n",ans);

    return ;

}

巴特西

1705. [Usaco2007 Nov]Telephone Wire 架设电话线

最新文章

热门文章