$Making-the-Grade$Making−the−Grade

Description

链接
给出数列 $A$A, 求非严格单调递减或递增, 且 $S={\sum }_{i=1}^N\mid A_i-B_i\mid$S=∑i=1N​∣Ai​−Bi​∣ 最小的序列 $B$B

Solution

以 $B$B非严格单调递增为例, 考虑已经选了 $N$N个数, 最小值怎么取

若 $N=1$N=1, $A_1=B_1$A1​=B1​ 时 $S$S 最小;
若 $N\>1$N>1时, 假如前面已经选择了 $N-1$N−1个数取得了最小值, 考虑怎么取第 $N$N个数
-　　当 $A_i\>=B_{i-1}$Ai​>=Bi−1​时, $B_i=A_i$Bi​=Ai​时显然最优.
-　　当 $A_i\&lt;B_{i-1}$Ai​<Bi−1​时,
　　　　 -　 使 $B_i=A_i$Bi​=Ai​;
.　　　　-　 将 $B_k,B_{k+1}...,B_i$Bk​,Bk+1​...,Bi​全部赋值为 $A_k,A_{k+1}...,A_i$Ak​,Ak+1​...,Ai​的中位数(根据货仓选址问题显然选择中位数最佳 )

若按照上方直接模拟, 复杂度不可估量(其实是懒得算, 反正过不了)
但是可以得出结论 : $B$B数列中的每个数必定都为 $A$A数列中的元素

于是可以考虑 $dp$dp
以 $dp$dp到第 $i$i位为阶段, 为了转移, 状态可设 $dp[i,j]$dp[i,j]表示 $B$B的最后一个元素为 $A_j$Aj​时的 $S_{min}$Smin​,
转移方程: $dp[i,j]=max\left\{dp\right[i-1,k]+\mid A_i-A_j\mid \}$dp[i,j]=max{dp[i−1,k]+∣Ai​−Aj​∣}… $A_k\&lt;=A_j$Ak​<=Aj​
时间复杂度 $O\left(N^3\right)$O(N3)
将 $A$A拷贝到 $C$C数组, $sort$sort排序后保持决策集合增长时新决策的单调性
即可实现 $O\left(N^2\right)$O(N2)
具体可以看下方代码 $\downarrow$↓

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define reg register

const int maxn = 2005;

int N;
int A[maxn];
int C[maxn];
int dp[maxn][maxn];

int main(){
        scanf("%d", &N);
        for(reg int i = 1; i <= N; i ++) scanf("%d", &A[i]), C[i] = A[i];
        std::sort(C+1, C+N+1);
        memset(dp, 0x3f, sizeof dp);
        for(reg int i = 1; i <= N; i ++) dp[0][i] = 0;
        for(reg int i = 1; i <= N; i ++){
                int minn = 0x3f3f3f3f;
                for(reg int j = 1; j <= N; j ++){
                        minn = std::min(minn, dp[i-1][j]);
                        dp[i][j] = std::min(dp[i][j], minn + abs(A[i] - C[j]));
                }
        }
        int Ans = 0x3f3f3f3f;
        for(reg int i = 1; i <= N; i ++) Ans = std::min(Ans, dp[N][i]);
        std::reverse(C+1, C+N+1);
        memset(dp, 0x3f, sizeof dp);
        dp[0][0] = 0;
        for(reg int i = 1; i <= N; i ++){
                int minn = 0x3f3f3f3f;
                for(reg int j = 1; j <= N; j ++){
                        minn = std::min(minn, dp[i-1][j]);
                        dp[i][j] = std::min(dp[i][j], minn + abs(A[i] - C[j]));
                }
        }
        for(reg int i = 1; i <= N; i ++) Ans = std::min(Ans, dp[N][i]);
        printf("%d\n", Ans);
        return 0;
}