【题意】
有n块高低不同的地面,每让一块高度改变1则需支付1的代价,问将地面高度变为不上升或不下降序列所需最小代价
【输入】
第一行一个n
接下来n行每行一个数字表示该块地面的高度
【输出】
一个数字,表示最小代价
离散高度后dp
用f[i][j]表示考虑钱i块地面,当前地面高度离散后为j的所需最小代价
f[i][j]=min(f[i-1][k]+abs(h[i]-num[j]))(若为上升序列则k<=j,若为下降序列则k>=j)
枚举k比较慢所以预处理一下
由于f[i]的取值只跟f[i-1]有关,所以运用滚动数字
program poj3666;
var
n,i,j,k,tot,o,ans:longint;
......
阅读全文