当前位置: 代码迷 >> 综合 >> POJ 3612/ P2885 [USACO07NOV]电话线Telephone Wire
  详细解决方案

POJ 3612/ P2885 [USACO07NOV]电话线Telephone Wire

热度:0   发布时间:2024-01-15 08:12:32.0

题目描述

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;  
}