poj3612Telephone Wire<DP>

链接:http://poj.org/problem?id=3612

题意:

有N根柱子, 高度确定, 现在要使它们连接起来,划分为相邻的柱子的高度差 h *C, 还可以加高度, 花费为所加高度 x 的平方;求最小花费;

思路:

朴素的想法: 用dp[i][j] 代表第 i 根柱子高度为 j 时的最小花费, 那么 dp[i][j] = dp[i-1][k] + abs( j-k ) * C + (j-a[i])^2;

复杂度为 10^5*10^2*10^2 = 10^9  TLE 无压力 ;

再来看上面的式子, 去绝对值得到  dp[i][j]=dp[i][k]+(j-k)*C+j-a[i]^2 = dp[i][k]-K*C+j*C+( j-a[i] )^2; ( j>k )

　　　　　　　　　　　　　　　 dp[i][j]=dp[i][k]+(k-j)*C+j-a[i]^2 = dp[i][k]+K*C-j*C+( j-a[i] )^2; ( j<K)   

对于 j 来说 j*C+( j-a[i] )^2 为定值 所以我们只要考虑 dp[i][k]-K*C ( j>K ) 和 dp[i][k] + K*C (j<K)

我们可以用另外两个数组分别保存他们的最优解, 即可得到 dp 的最优解 ;

low[i-1][k]=dp[i - 1][k] - c * k   ;  high[i - 1][k] = dp[i - 1][k] + c * k ;

对于相同的 i, 它们都只与当前的k有关, 且可以互相转化,所以可以只开一维;

则 : dp[i][j] = min(low[i - 1][k] + c * j + (j - a[i]) ^ 2)  , high[i - 1][k] - c * j + (j - a[i]) ^ 2));

#include<cstdio>
 #include<algorithm>
 #include<cstring>
 using namespace std;
 int dp[102],low[102],high[102];
 const int inf=1<<30;
 
 int main()
 {
     int n,c;
     while(scanf("%d%d",&n,&c)!=EOF){
         int h;
         memset(low,0x3f,sizeof(low));
         memset(high,0x3f,sizeof(high));
         
         for(int i=1; i<=n; i++){
            scanf("%d",&h);
            if( i==1 ){
                for(int i=0; i<h; i++)
                     dp[i]=inf;
                 for(int i=h; i<=100; i++)
                     dp[i]=(i-h)*(i-h);
            }
            else{
                memset(dp,0x3f,sizeof(dp));
                 for(int j=h; j<=100; j++)
                    dp[j]=min(j*c+(h-j)*(h-j)+low[j],(h-j)*(h-j)-j*c+high[j]);
            }
            
             low[0]=dp[0];
             for(int i=1; i<=100; i++)
                 low[i]=min(dp[i]-i*c,low[i-1]);
             high[100]=dp[100]+100*c;
             for(int i=99; i>=0; i--)
                 high[i]=min(dp[i]+i*c,high[i+1]);     
         }
         int ans=inf;
         for(int i=0;i<=100;i++)
             ans=min(ans,dp[i]);
         printf("%d\n",ans);
     }
     return 0;
 }