Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
本小菜说说这道题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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator