USACO 2007 Nov Gold 1.Telephone Wire

2014.12.23 16:50 Tue| 6 visits oi_2015| 2015_刷题日常| Text

忍了好久,下了N次决心后终于开始刷USACO题了哈哈哈哈哈哈……

Solution

当然是DP。据说很像NOIP2014 D1T3的傻鸟。好吧……

用 $f(n,h)$ 表示将第n个位置的电线杆加高到h处时的最小花费。对于所有 $h'$ ,

不幸的是,这一算法时间复杂度为 $\mathcal O(NH^2)$。很显然,可以换一种表达形式:

这样可以用一个单调队列?来优化DP。总时间复杂度 $\mathcal O(NH)$ 。30行的代码好令人开心的说呢。

Code

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sqr(x) ((x)*(x))

int n,c,h[100005],f[105],a[105],b[105];

int main()
{
    cin>>n>>c;
    for(int i=1;i<=n;i++)
        scanf("%d",&h[i]);
    for(int i=1;i<=n;i++)
    {
        a[0]=inf;
        for(int j=1;j<=100;j++)
            a[j]=min(f[j],a[j-1]+c);
        b[101]=inf;
        for(int j=100;j>=h[i];j--)
            b[j]=min(f[j],b[j+1]+c);
        for(int j=1;j<h[i];j++)
            f[j]=inf;
        for(int j=h[i];j<=100;j++)
            f[j]=sqr(j-h[i])+min(a[j],b[j]);
    }
    for(int i=h[n];i<=100;i++)
        f[1]=min(f[1],f[i]);
    cout<<f[1]<<endl;
}