题目描述
Farmer John's cows aregetting restless about their poor telephone service; they want FJ to replacethe old telephone wire with new, more efficient wire. The new wiring willutilize N (2 ≤ N ≤ 100,000) already-installed telephone poles, each with someheighti meters (1 ≤ heighti ≤ 100). The new wire will connect the tops of eachpair of adjacent poles and will incur a penalty cost C × the two poles' heightdifference for each section of wire where the poles are of different heights (1≤ C ≤ 100). The poles, of course, are in a certain sequence and can not bemoved.
Farmer John figuresthat if he makes some poles taller he can reduce his penalties, though withsome other additional cost. He can add an integer X number of meters to a poleat a cost of X2.
Help Farmer Johndetermine the cheapest combination of growing pole heights and connecting wireso that the cows can get their new and improved service.
给出若干棵树的高度，你可以进行一种操作：把某棵树增高h，花费为h*h。
操作完成后连线，两棵树间花费为高度差*定值c。
求两种花费加和最小值。
输入输出格式
输入格式：
* Line 1: Twospace-separated integers: N and C
* Lines 2..N+1: Linei+1 contains a single integer: heighti
输出格式：
* Line 1: The minimumtotal amount of money that it will cost Farmer John to attach the new telephonewire.
输入输出样例
输入样例#1： 复制
5 2
2
3
5
1
4
输出样例#1： 复制
15
算法分析：
设dp[i][j]为第i棵树的j高度的最小花费
状态转移方程：d[i][j]=min(d[i][j],d[i-1][k]+abs(j-k)*m+(a[i]-j)*(a[i]-j));
但如下代码交上去超时：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
using namespace std;
const double eps = 1e-8;
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 1e5 + 10;
const int MAXT = 10000 + 10;
#define N 110005
int n,c,h[N],dp[N][105];
inline void read(int &n)
{char c='+';bool flag=0;n=0;while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}while(c>='0'&&c<='9')n=n*10+c-48,c=getchar();
}
int main()
{ while(scanf("%d%d",&n,&c)!=EOF) { int maxh=0;memset(dp,INT_INF,sizeof(dp));for(int i=1;i<=n;i++){read(h[i]);maxh=max(h[i],maxh);}for(int i=h[1];i<=maxh;i++){dp[1][i]=(i-h[1])*(i-h[1]);}for(int i=2;i<=n;i++)for(int j=h[i];j<=maxh;j++)for(int k=h[i-1];k<=maxh;k++){dp[i][j]=min(dp[i][j],(j-h[i])*(j-h[i])+dp[i-1][k]+abs(j-k)*c);}int ans=INT_INF;for(int i=h[n];i<=maxh;i++){ans=min(ans,dp[n][i]);}printf("%d",ans);} return 0;
}
所以需要优化，
dp[i][j]=min( (j-a[i])^2+f[i-1][k]+|j-k|*c )(j>=a[i])
当(j>=k) 时，dp[i][j]=(j-a[i])^2+j*c+min(f[i-1][k]-k*c) (j>=k)
当(j<k)时， dp[i][j]= (j-a[i])^2-j*c+min(f[i-1][k]+k*c) (j<k)
设high[j]=min(dp[i-1][k]-k*c) (j>=k)
low[j]=min(dp[i-1][k]+k*c) (j<k)
方程就变为dp[i][j]=(j-a[i])^2+min(high[j]+j*c,low[j]-j*c);
AC代码
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
using namespace std;
const double eps = 1e-8;
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 1e5 + 10;
const int MAXT = 10000 + 10;
#define N 110005
int n,c,h[N],dp[N][105],low[105],high[105];
inline void read(int &n)
{char c='+';bool flag=0;n=0;while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}while(c>='0'&&c<='9')n=n*10+c-48,c=getchar();
}
int main()
{ while(scanf("%d%d",&n,&c)!=EOF) { int maxh=0;memset(dp,INT_INF,sizeof(dp));memset(low,INT_INF,sizeof(low));memset(high,INT_INF,sizeof(high));for(int i=1;i<=n;i++){read(h[i]);maxh=max(h[i],maxh);}for(int i=1;i<=maxh;i++)dp[0][i]=0;for(int i=1;i<=n;i++){for(int t=INT_INF, j=maxh;j>0;j--){low[j]=t=min(t,dp[i-1][j]+c*j);}for(int t=INT_INF, j=1;j<=maxh;j++){high[j]=t=min(t,dp[i-1][j]-c*j);}for(int j=h[i];j<=maxh;j++)dp[i][j]=(j-h[i])*(j-h[i])+min(high[j]+j*c,low[j]-j*c) ;}int ans=INT_INF;for(int i=h[n];i<=maxh;i++){ans=min(ans,dp[n][i]);}printf("%d",ans);} return 0;
}