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