题解 P2885 【[USACO07NOV]电话线Telephone Wire】
asuldb
2018-05-23 16:52:51
先说说暴力做法吧，我们用f[i][j]表示前i棵树，其中第i棵树高度为j时的最小花费，于是我们有一个很好推的的dp式子了
$$f[i][j]=(j-h[i])^2+min(f[i-1][k]+c*abs(j-k))$$
于是对于每一棵树的每一种高度我们要枚举前面的那一棵树的所有高度来算一个最小值，于是复杂度大概是$O(n*max(h)^2)$，在$N ≤ 100,000$，树的高度小于$100$的数据下靠着比较优秀的常数以及O2卡了过去
暴力代码：
```cpp
// luogu-judger-enable-o2
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#define re register
#define mp make_pair
#define xx first
#define y second
#define maxn 100001
#define int long long
#define inf 9999999999
using namespace std;
int f[maxn][101],h[maxn];
int n,c,maxx,mid;
inline int read()
{
char c=getchar();
int x=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-48,c=getchar();
return x;
}
signed main()
{
n=read();
c=read();
for(re int i=1;i<=n;i++) h[i]=read(),maxx=max(h[i],maxx);
for(re int i=1;i<=n;i++)
for(re int j=0;j<=100;j++) f[i][j]=inf;
for(re int i=h[1];i<=maxx;i++)
f[1][i]=(i-h[1])*(i-h[1]);
for(re int i=2;i<=n;i++)
{
for(re int j=h[i];j<=maxx;j++)
{
for(re int k=h[i-1];k<=maxx;k++)
{
f[i][j]=min(f[i][j],f[i-1][k]+c*abs(j-k)+(j-h[i])*(j-h[i]));
}
}
}
int ans=inf;
for(re int i=h[n];i<=maxx;i++)
ans=min(ans,f[n][i]);
cout<<ans<<endl;
return 0;
}
```
那么这个复杂度其实是明显不对的，我们用暴力刚过去也主要靠洛谷评测机的性能比较优秀
于是我们再去看dp的方程
有两种情况：
$$f[i][j]=(j-h[i])^2+min(f[i-1][k]-c*k+c*j)\ \ (k<j)$$
$$f[i][j]=(j-h[i])^2+min(f[i-1][k]+c*k-c*j)\ \ (k>j)$$
后面那些东西显然可以用单调队列优化一下
那么我们可以分类讨论一下，就可以解决这个恶心的绝对值了
至于我们如何分类讨论呢，我们只要巧妙的改变循环的顺序就可以做到这一点了
也就是说我们正着循环再倒着来一遍就好了
至于具体怎么搞，代码里说的应该很清楚了
于是就是代码了，大概可以跑到最优解第二吧
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<fstream>
#define re register
#define inf 999999999
using namespace std;
int f[2][101],n,c;
int h[100001];
int now,m;
int ans=inf;
inline int read()
{
char c=getchar();
int x=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-48,c=getchar();
return x;
}
int main()
{
n=read();
c=read();
now=1;
for(re int i=1;i<=n;i++) h[i]=read(),m=max(m,h[i]);
for(re int i=0;i<=m;i++) f[0][i]=f[1][i]=inf;
for(re int i=h[1];i<=m;i++) f[now][i]=(i-h[1])*(i-h[1]);
//这里其实并没有使用真正单调队列的必要，我们只需要存好最小值就好了
for(re int i=2;i<=n;i++)
{
now^=1;
int k=inf;
for(re int j=h[i-1];j<=m;j++)
{
k=min(k,f[now^1][j]-j*c);
if(j>=h[i]) f[now][j]=k+(j-h[i])*(j-h[i])+c*j;
}
//这里对应的方程其实就是f[i][j]=(j-h[i])^2+min(f[i-1][k]-c*k+c*j) (k<j)
//因为这里正序枚举j可以保证j一定大于等于k的高度
k=inf;
for(re int j=m;j>=h[i];--j)//至于这里为什么是枚举到h[i],而不是h[i-1]
//我们可以想啊，如果h[i-1]大于h[i],这里的循环也枚举到h[i-1]
//那么f[now]从h[i-1]到h[i]的值并没有被更新，这显然是是不行的
//至于h[i-1]小于h[i]并没有什么关系，因为我们并不能使h[i]的高度减小
{
k=min(k,f[now^1][j]+j*c);
f[now][j]=min(f[now][j],k-c*j+(j-h[i])*(j-h[i]));
}
//这里对应的方程其实就是f[i][j]=(j-h[i])^2+min(f[i-1][k]+c*k-c*j) (k>j)
// 因为这里的倒叙枚举可以保证j一定小于等于k的高度
for(re int i=0;i<=m;i++) f[now^1][i]=inf;
//记得把上一层数组初始化，我们下次又要用这一层了
}
for(re int i=h[n];i<=m;i++)
ans=min(ans,f[now][i]);
cout<<ans<<endl;
return 0;
}
```