codevs2572 路面修整

codevs2572 路面修整

原题地址

看数据范围，猜出正解应该是动规；再看那巨多无比的0。。。离散化吧骚年！

Point.1 离散化

由于高度的数据范围过于震撼，显然无法作为状态，所以考虑用b[i]来表示第i高||低（根据题意需要跑两遍取较小值）的路段的高度，这样就从1,000，000，000浓缩成了2,000，可以用二维数组存下。

Point.2 状态

Dp[i][j]表示前i个路段有序，第i个路段高度为b[j]。由于要将路面修整为单调上升的数列（单调下降也一样，先以单增为例），因此我们可以知道，修整后的路面一定是原路面的某个值，因此枚举j可以遍历所有情况。至于证明？显然啊。。。如果非要证，可以参考cgk的博客（打广告不要钱）：

/

Point.3 转移

dp[i][j-1] 枚举所有j取最小值嘛。。。

dp[i-1][j]+abs(b[j]-a[i]) 修整第i段的路面

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define inf 2100000000;
using namespace std;
long long dp[2010][2010],a[2010],b[2010];
bool cmp(int a,int b) 
{return a>b;
}int main()
{int n;scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%lld",&a[i]);b[i]=a[i];}for (int i=1;i<=n;i++) dp[i][0]=inf;sort(b+1,b+n+1);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)dp[i][j]=min(dp[i][j-1],dp[i-1][j]+abs(b[j]-a[i]));long long ans=dp[n][n];sort(b,b+n+1,cmp);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)dp[i][j]=min(dp[i][j-1],dp[i-1][j]+abs(b[j]-a[i]));	ans=min(dp[n][n],ans);printf("%lld",ans);return 0;
}