【HZOI 2016】架设电话线

题解 HZOI 学习

题面

第一眼

一句话，就是求这波操作的最小花费。
首先，因为是最优化问题，而且我们看到i的状态的只受i-1的影响且只影响i+1的状态，这符合最优子结构性质。然后我们看一眼那些神奇的转移，发现状态太多了搜索无处下手。那就只能用dp了
虽然动态规划一生之敌
在看题面时我们可以注意到一点，就是题中本该只作为一个权值的h[i]异常的小，这可以启发我们将h值作为一个状态考虑到我们的dp中。
那么就这么决定了，我们dp。

思考

考虑dp的状态，考虑到处理到第i位时，现在的花费不仅仅与位数有关，而且还与当前我们选择的i根柱子的高度有关，于是我们考虑到用一个二维数组dp[i][j]来表示当前处理，其中，i代表处理到第i位且当前这根柱子高度为j的最小花费。
既然确定了状态，考虑其他的：

1.初始化
由于我们每一个状态都由上一个状态转移而来，因此我们只需要考虑初始化i=1的状态
当i=1时，：f[1][j]=(j-h[i])^2或 f[1][j]=inf
因为我们只能进行第二个操作也就是加高高度,所以h[1]以下的无法达到初始为inf

2.转移
在题中转移只可以从i-1转移到i，所以可以较快的想出来dp方程

f[i][j]=min(f[i-1][k]+c*abs(j-k))+(j-h[i])^2 ,其中(j>=h[i])
如果就这么直接转移，时间复杂度会变为O(n*maxh^2)可以拿到70分。
但是由于j，k大小关系的不同实际上会有两种转移方式
f[i][j]=min(f[i-1][k]+j*C-k*C)+(j-h[i])^2 (j>=k)
f[i][j]=min(f[i-1][k]-j*c+k*c)+(j-h[i])^2 (j<k)
现在令temp[k]为f[i-1][k]±k
提取出同类项后有
f[i][j]=min(temp[k])+X其中X为一个常量。
那么推出这个后有什么用呢？
我们可以发现f[i][j]只需要分情况取最小值就可以求出了！
分情况取最小值操作可以在我们递增j时顺便进行，这样下来，整体复杂度就减小到了O(n*maxh)，可以得到满分

3.答案
根据我们所定义的状态，我们最终的答案保存在f[n][k]，其中k>=h[n]

细节
不过现在就说万事大吉未免太早，因为我们还有几个编码细节需要注意。

(1).初始最大值
我们一切转移都是使用函数min的，再定义全局变量时一定要记得初始最大值，不然……你自己试试

(2).转移条件
一定要认真读题，题中说电线杆只可以加高！

(3).注意小细节
每个人的程序都有自己的小细节，注意自己具体实现方法的细节就可以了。

代码

上面解释我认为足够详细，所以代码中不再给出注释

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=100010,maxh=110;
int h[maxn],c,f[maxn][maxh],n;
void beg(){
    freopen("phonewire.in","r",stdin);
    freopen("phonewire.out","w",stdout);
}
int calval(int x){
    return x*x;
}
int main(){
    beg();
    scanf("%d%d",&n,&c);
    for (int i=1;i<=n;i++){
        scanf("%d",&h[i]);
    }
    memset(f,0xff/3,sizeof(f));
    for (int i=h[1];i<=100;i++) f[1][i]=calval(h[1]-i);
    for (int i=2;i<=n;i++){
    int temp=1e9;
    for (int j=0;j<=100;j++){
        if (j>=h[i-1]) temp=min(temp,f[i-1][j]-j*c);
        if (j>=h[i]) f[i][j]=min(f[i][j],temp+calval(j-h[i])+j*c);
    }
    temp=1e9;
    for (int j=100;j>=0;j--){
        if (j>=h[i-1]) temp=min(temp,f[i-1][j]+j*c);
        if (j>=h[i]) f[i][j]=min(f[i][j],temp+calval(j-h[i])-j*c);
    }
    }
    int t=1e9;
    for (int i=h[n];i<=100;i++){
        t=min(t,f[n][i]);
    }
    printf("%d\n",t);
}

几个鸡肋的小优化

1.题中因为每个状态只需要上一个状态，所以可以使用滚动数组
我也不知道数据范围这么小为什么要用滚动数组
2.题中f[i][j]满足单调性所以可以考虑单调队列优化。
但是实际上只要记录一个最小值就好了因为根本不需要弹出操作
3.每次其实可以只扫一半
反正不会爆随便啦