Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

本小菜说说这道题

Posted by xiao_wu at 2010-07-29 11:14:37 on Problem 3666
 O(n ^ 2) 的dp  Memory: 47432K  Time: 47MS 
 1、先将数组离散化,那么不管多高,数据最多有2000个点
 2、3个数组:
   (1) dp[ 第几个点 ][ 离散后的高度i ] 表示最优值
   (2) mi[ 第几个点 ][ 离散后的高度i ] 表示i之前的dp最小值
   (3) mx[ 第几个点 ][ 离散后的高度i ] 表示i之后的dp最小值
 3、那么就有
    递增:dp[i][h] = mi[i - 1][h] + abs( h - height[i点高度] )
    递减: dp[i][h] = mx[i - 1][h] + abs( h - height[i点高度] )
 4、由于h是经过离散的高度,假设离散数组为c[ 离散后高度 ] ,表示对印的高度,则有
    abs( c[ h ] - height[ i点高度 ] )
 5、两重循环,更新mi 和 mx 的值,例如:
    for(int i = 1; i < n; i ++)
    {
        for(int j = 0; j < len; j ++)
        {
            dp[i][j] = mi[i - 1][j] + abs(c[j] - height[i]);
            mi[i][j] = dp[i][j];
            if(j > 0) mi[i][j] = min(mi[i][j - 1] , dp[i][j]);
        }
    }
 6、由于递增递减是不能同时发生的,所以要分别写,并且mx数组的更新与mi数组的更新不同

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator