Making the Grade 路面修整

Making the Grade 路面修整

「POJ 3666」Making the Grade 路面修整

1 算法标签

dp动态规划，滚动数组优化

2 题目难度

提高/提高+

3 题面

「POJ 3666」Making the Grade 路面修整

4 分析题面

4.1 简要描述

给出数列 A A A, 求非严格单调不上升或单调不下降, 且 S = ∑ i = 1 N ∣ A i − B i ∣ S=sum^N_{i=1}|A_i-B_i| S=∑i=1N​∣Ai​−Bi​∣ 最小的序列 B B B，输出 S S S

4.2 模型转换

输入N, 然后输入N个数，求最小的改动这些数使之成非严格递增或非严格递减即可

5 问题分析

以B为非严格单调递增为例

考虑已经选了 n n n个数

• 若 n = 1 n=1 n=1， A 1 = B 1 A_1=B_1 A1​=B1​时 S S S最小为 ∣ A 1 − B 1 ∣ |A_1-B_1| ∣A1​−B1​∣

• 若 n > 1 n>1 n>1，前面已经选择了 n − 1 n-1 n−1个数，取得了最小值，考虑怎么取第 n n n个数

  • 若 A i ≥ B i − 1 A_i≥B_{i-1} Ai​≥Bi−1​， B i = A i B_i=A_i Bi​=Ai​显然最优

  • 若 A i < B i − 1 A_i<B_{i-1} Ai​<Bi−1​，

    • B i = A i B_i=A_i Bi​=Ai​

    • 将 B k , B K + 1 , . . . , B i B_k,B_{K+1},...,B_i Bk​,BK+1​,...,Bi​都赋值为 A k , A k + 1 , . . . , A i A_k,A_k+1,...,A_i Ak​,Ak​+1,...,Ai​的中位数

      口胡证明：

      我们可以将 B k , B K + 1 , . . . , B i B_k,B_{K+1},...,B_i Bk​,BK+1​,...,Bi​标记在数轴上，再将 A k , A k + 1 , . . . , A i A_k,A_k+1,...,A_i Ak​,Ak​+1,...,Ai​标记上

      那么，其实 S S S的几何含义就是每一组 A i A_i Ai​到 B i B_i Bi​的距离之和

      我们也学过绝对值问题： ∣ x − k 1 ∣ + ∣ x − k 2 ∣ + ∣ x − k 3 ∣ . . . |x-k_1|+|x-k_2|+|x-k_3|... ∣x−k1​∣+∣x−k2​∣+∣x−k3​∣...的最小值这种

      其实和这里的 S S S是没有任何区别的

      所以，我们知道零点分段法

      就是取中位数（就是使每个绝对值内部为0的x答案数组的中位数）

      可以使得绝对值之和最小

      1. 如果x在两个 k k k之间,那么无论x在哪,距离之和都是这两个k的距离
      2. 如果在这两个 k k k之外,那么距离之和则为两个k距离加上两倍的x距近的k的距离，肯定小于第一种情况

      那么我们只要尽量让 x x x在越多的 k k k之间即可

      那么最佳x在图中就是 4 4 4,如果 k k k的个数为偶数n,则是 k n / 2 k_{n/2} kn/2​和 K n / 2 + 1 K_{n/2+1} Kn/2+1​之间

      综上，选择中位数最佳

通过综上分析，我们直接暴力肯定是不行的~~（这个复杂度直接爆掉了）~~

但是！

我们可以得到一个结论：

B数列中的每个数必定都为A数列中的元素

所以，我们可以考虑dp

阶段：到第 i i i位

状态： d p i , j dp_{i,j} dpi,j​表示以 B j B_j Bj​结尾的 S m i n S_{min} Smin​

B数组是A的复制排序处理过后的数组

d p [ i ] [ j ] dp[i][j] dp[i][j]表示把前i个数变成不严格单调递增且第 i i i个数变成原来第 j j j大的数的最小代价

转移方程： d p i , j = m i n ( d p i − 1 , j ) + ∣ A i − B j ∣ , 其 中 1 ≤ j ≤ n dp_{i,j}=min(dp_{i-1,j})+|A_i-B_j|,其中1≤j≤n dpi,j​=min(dpi−1,j​)+∣Ai​−Bj​∣,其中1≤j≤n

6 实现细节

6.1 滚动数组

开二维数组有点浪费欸

那怎么办呢？

由于我们只用到了 i − 1 i-1 i−1

所以，我们考虑用滚动数组优化，用位运算符&来记录，这样就只用了 0 / 1 0/1 0/1来表示，重复利用，节省空间

i i i& 1 1 1的效果和 i i i% 2 2 2的效果是一样的，但是 i i i& 1 1 1要快一点

且这种方式比直接写0/1少了一个不断交换的过程

窝jio得这个还是很香的

将 i − > i i->i i−>i & 1 1 1， i − 1 − > ( i − 1 ) i-1->(i-1) i−1−>(i−1)& 1 1 1

方程就变成了这样：

d p [ i dp[i dp[i& 1 ] [ j ] = m i n ( d p [ ( i − 1 ) 1][j]=min(dp[(i-1) 1][j]=min(dp[(i−1)& ] [ k ] ) + ∣ A [ i ] − B [ j ] ∣ , 其 中 1 ≤ j ≤ n , 1 ≤ k ≤ j ][k])+|A[i]-B[j]|,其中1≤j≤n,1≤k≤j ][k])+∣A[i]−B[j]∣,其中1≤j≤n,1≤k≤j

6.2 最小值

但是这个复杂度。。

看上去好像是3层循环，就是 O ( n 3 ) O(n^3) O(n3)啊

在 n < = 2000 n<=2000 n<=2000 的时候就已经game over了，显然不行啊

这个问题应该有手就行吧

其实只要一边更新 m i n ( f [ i − 1 ] [ k ] ) min(f[i-1][k]) min(f[i−1][k])一般算当前的 f [ i ] [ j ] f[i][j] f[i][j]就行

（因为 k k k只到 j j j）

6.3 降序

不严格单调不上升的情况也一样

更加方便的是可以把 B B B数组从大到小排序后，做单调不下降的dp就🆗了

7 代码实现（增加代码注释）

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+2;
int n,f[2][N],a[N],b[N],ans=0x3f3f3f3f;
bool cmp1(int x,int y){return x<y;
}//升序 
bool cmp2(int x,int y){return x>y;
}//降序 
void work(){for(int i=1;i<=n;i++){f[1][i]=abs(a[1]-b[i]);}//边界条件for(int i=2;i<=n;i++){int minn=f[(i-1)&1][1];for(int j=1;j<=n;j++){minn=min(minn,f[(i-1)&1][j]);//边更新边求f[i&1][j]=minn+abs(a[i]-b[j]);//滚动数组 }} for(int i=1;i<=n;i++){ans=min(ans,f[n&1][i]);}//求答案
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];//拷贝到b数组}sort(b+1,b+1+n,cmp1);//从小到大 work(); //dp计算sort(b+1,b+1+n,cmp2);//从大到小 work();//直接就是一样的啊printf("%d",ans);//输出最小return 0;
}

8 总结

1. 最大的收获：dp！！！

2. 新鲜的知识：更优秀的滚动数组写法

3. 相似的题目：CF #371 div.1 C Sonya and Problem Wihtout a Legend