【训练题】路面修整[1]

【训练题】路面修整[1]

【问题描述】

　　FJ打算好好修一下农场中某条凹凸不平的土路。按奶牛们的要求，修好后的路面高度应当单调上升或单调下降，也就是说，高度上升与高度下降的路段不能同时出现在修好的路中。

　　整条路被分成了 N 段，N 个整数 A[1]，…，A[N] 依次描述了每一段路的高度。FJ希望找到一个恰好含 N 个元素的不上升或不下降序列B[1]，…，B[N]，作为修过的路中每个路段的高度。

　　由于将每一段路垫高或挖低一个单位的花费相同，修路的总支出可以表示为：|A[1]-B[1]|+|A[2]-B[2]|+…+|A[N]-B[N]|。

　　请你计算一下，FJ在这项工程上的最小支出是多少。FJ向你保证，这个支出不会超过2^31-1。

【输入格式】  

　　第1行：输入1个整数N；
　　第2..N+1行：第i+1行为1个整数A[i]

【输出格式】  

　　第1行：输出1个正整数，表示FJ把路修成高度不上升或高度不下降的最小花费。

【输入样例】  

7
1
3
2
4
5
3
9

【输出样例】  

3

【样例解释】  

　　FJ将第一个高度为3的路段的高度减少为2，将第二个高度为3的路段的高度增加到5，总花费为|2-3|+|5-3|=3，并且各路段的高度为一个不下降序列1,2,2,4,5,5,9。

【数据范围】  

1<=N<=2,000
0<=A_i<=1,000,000,000
思路
并不能算严格的子集型动态规划，归在这里只是因为有选不选的特性
题目大意为找非递减子序列，代价最小(左右都可开始)
从最开始的暴力dp思考
f(i,j)表示将i修改成j的最小代价,j可以达到10^9，很显然只能得20-30分
考虑状态的优化
每一次需要改的数，我们一定可以从原序列中找到，因为是非递减，所以当出现不满足情况的时候
修改中间的永远比修改后面的更优，因为代价相同时修改后面的具有后效性
而修改的值又以在原序列中出现过为最优
所以状态函数可以修改为
f(i,j)表示将a[i]修改成b[j]的最小代价
b[j]为原序列的递增序列(排序预处理)
转移方程很显然就为
f(i,j)=min(f(i,j),f(i-1,k)) 1<=k<=j
此时为O(n^3)
依旧无法通过
但此时就可以加数组或者单调优先队列优化成O(n^2)的算法

此时需要一提的是
状态转移方程可以设为
f(i,j)=min(f(i,j-1),f(i-1,j))
这就是归于子集型动态规划的原因，还有一次遇见是在飞扬的小鸟
为什么?
这就是一个完全背包问题
当时经过滚动数组的优化无法看出方程是什么,原方程其实就是f(i,j)=max(f(i,j-v[i],f(i-1,j))
之所以可以进行这样的优化，是因为经过逆推，会发现f(i,j-2*v[i])f(i,j-3*v[i])…..
所以调用f(i,j-v[i])的时候相当于已经调用了前面所有的f(i,k)
类似于多设了一个数组
代码如下

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
#define maxn 2005
int f[maxn][maxn],n,a[maxn],b[maxn];
void init()
{scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];}   
}
void solve()
{sort(b+1,b+n+1);for (int i=1;i<=n;i++)f[i][0]=1e9;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)f[i][j]=min(f[i][j-1],f[i-1][j]+abs(a[i]-b[j]));int ans=f[n][n];for (int i=1;i<=n;i++)f[i][0]=1e9;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)f[i][j]=min(f[i][j-1],f[i-1][j]+abs(a[i]-b[n-j+1]));ans=min(ans,f[n][n]);printf("%d",ans);
}
int main()
{freopen(&#","r",stdin);init();solve();return 0;
}