P2893 [USACO08FEB]Making the Grade G
P8107
·
·
题解
\color{blue}{\text {pwp }~{\to\textbf{My blog}\gets}}~\text{qwq}
题解 P2893
一道 DP。
1.状态
影响决策的两个因素只有已完成构造数个数和上一个元素，所以我们设 f(i,j) 表示已经完成前 i 个数的构造，构造出的 B 数组的第 i 位为 j 时的最小花费。
### 2.转移方程
可以把题目分为**构造单调不升序列**和**构造单调不降序列**两部分，最终答案取最小值即可，现在先考虑**构造单调不降序列**。
可以想到一个方程：$f(i,j)=\min\limits_{0 \leq k \leq j}\{f(i-1,k)+|A_i-j|\}$。
但是这样的话复杂度是 $O(n^3)$ 的，显然会 TLE，所以我们使用 传 统 艺 能：可以发现在枚举 $j$ 时 $i$ 的值是不变的，所以我们可以完全不用枚举 $k$，在枚举 $j$ 的时候顺便存储 $f(i-1,k)$ 的最小值即可。具体可以看代码。
而单调不升序列怎么构造？可以把原序列翻转过来构造单调不降序列即可。
## 代码
```cpp
//P2893
#include <bits/stdc++.h>
using namespace std;
const int N=2010;
int n,m,a[N],dct[N],dp[N][N],ans=0x3f3f3f3f;
int main(){
cin>>n;
for(int i=1; i<=n; ++i) cin>>a[i], dct[i]=a[i];
sort(dct+1,dct+n+1), m=unique(dct+1,dct+n+1)-(dct+1); //离散化
memset(dp,0x3f,sizeof(dp)), dp[0][0]=0; //dp 数组初始化，因为求最小值所以全部初始为 inf，边界就是 dp[0][0]=0
for(int i=1; i<=n; ++i){
int t=dp[i-1][0];//记录 dp[i-1][k] 的最小值，进行转移
for(int j=1; j<=m; ++j){
t=min(t,dp[i-1][j]);// 更新最小值
dp[i][j]=t+abs(a[i]-dct[j]);//转移
}
}
for(int i=1; i<=m; ++i) ans=min(ans,dp[n][i]);//取答案
reverse(a+1,a+n+1); //翻转序列，以下步骤同上
memset(dp,0x3f,sizeof(dp)), dp[0][0]=0;
for(int i=1; i<=n; ++i){
int t=dp[i-1][0];
for(int j=1; j<=m; ++j){
t=min(t,dp[i-1][j]);
dp[i][j]=t+abs(a[i]-dct[j]);
}
}
for(int i=1; i<=m; ++i) ans=min(ans,dp[n][i]);
cout<<ans<<'\n';
return 0;
}
```