【POJ3612】【USACO 2007 Nov Gold】 1.Telephone Wire 动态调节

意甲冠军：

一些树高给出。行一种操作：把某棵树增高h，花费为h*h。

操作完毕后连线，两棵树间花费为高度差*定值c。

求两种花费加和最小值。

题解：

跟NOIP2014 D1T3非常像。

暴力动规是O(1*10^9)会T

所以单调队列一下，每颗树扫两遍结束。

完事，看水代码吧。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 101000

#define M 105

#define inf 0x3f3f3f3f

using namespace std;

int f[2][M],g[2][M],n,c;

int now,last;

int h[N];

int main()

{

//	freopen("test.in","r",stdin);

	int i,j,k;

	scanf("%d%d",&n,&c);

	for(i=1;i<=n;i++)scanf("%d",&h[i]);

	now=0,last=1;

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

	{

		now^=1,last^=1;

		int temp=inf;

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

		{

			temp=min(temp+c,f[last][j]);

			f[now][j]=temp+(j-h[i])*(j-h[i]);

		}

		temp=inf;

		for(j=1;j<=100;j++)

		{

			temp=min(temp+c,f[last][j]);

			f[now][j]=min(f[now][j],temp+(j-h[i])*(j-h[i]));

			if(j<h[i])f[now][j]=inf;

		}

	}

	int ans=inf;

	for(i=1;i<=100;i++)ans=min(ans,f[now][i]);

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

	return 0;

}