Making the Grade-蒲公英云

Making the Grade

给定长度为n的序列\(\{a_i\}\),求构造长度为n的递增序列\(\{b_i\}\)，求\(\sum_{i=1}^n|a_i-b_i|\)最小值，\(1 ≤ N ≤ 2,000\)。

解

首先空间与时间不支持你表现\(b_i\)填什么，于是猜测\(b_i\)必然填的为\(a_i\)里的数。

证明：

显然填到第1个数满足条件，

假设前i-1个数满足条件，且为最优解。

考虑现在填到第i个数，如果\(a_i\geq b_{i-1}\)，我们可以令\(b_i=a_i\)。

而如果\(a_i<b_{i-1}\)，要么是\(b_i=b_{i-1}\)更优，要么得把\(b_i\)下调到x，同理前面的数也要下调，而此时必然有一段数\(b_i\)是等于x，因为如果还可以下调达到更优，之前就可以这么做了，而这一段达到最优可以是这一段对应的\(a_i\)的中位数，所以无论如何，都满足题意，故成立。

法一：

考虑到\(b_i\)中含有\(a_i\)的段性，故设\(f_i\)表示考虑到\(b_i\),且\(b_i=a_i\)的所求最小值，设\(cost(j+1,i-1)\)表示i，j间填左边填一段\(a_j\),右边填一段\(a_i\)的最小值，于是我们有

\[f_i=\min_{j=1,a_j<a_i}^{i-1}(f_j+cost(j+1,i-1))\]

边界:\(f_0=0\)其余无限大

答案：\(\min_{i=1}^n(f_i+\sum_{j=i+1}^n|a_j-a_i|)\)

至于cost如何求，你只要维护分别维护只填\(a_i\)或者\(a_j\)前缀和，枚举中间点转移即可，最终时间复杂度\(O(n^3)\)。

参考代码：

#include <iostream> #include <cstdio> #include <cstring> #define il inline #define ri register #define intmax 0x7fffffff using namespace std; int A[2001],dp[2001],sl[2001], sr[2001]; il void read(int&); template<class free>il free Abs(free); template<class free>il free Min(free,free); int main(){ int n,i,j,k,l,ans(intmax); memset(dp,66,sizeof(dp)); read(n),dp[1]=0;for(i=1;i<=n;++i){ read(A[i]); for(j=1;j<i;++j){ if(A[j]>A[i])continue; sl[j]=sr[j]=0,l=intmax; for(k=j+1;k<i;++k)sl[k]=sl[k-1]+Abs(A[k]-A[j]); for(k=j+1;k<i;++k)sr[k]=sr[k-1]+Abs(A[k]-A[i]); for(k=j;k<i;++k) l=Min(l,sl[k]-sl[j]+sr[i-1]-sr[k]); dp[i]=Min(dp[i],dp[j]+l); } } for(i=1;i<=n;++i){ j&=0; for(k=i+1;k<=n;++k) j+=Abs(A[k]-A[i]); ans=Min(ans,j+dp[i]); }printf("%d",ans); return 0; } template<class free> il free Min(free a,free b){ return a<b?a:b; } template<class free> il free Abs(free x){ return x<0?-x:x; } il void read(int &x){ x&=0;ri char c;while(c=getchar(),c<'0'||c>'9'); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); }

法二：

最直接的感觉是要想维护递增，我必然要表现出这里填什么，预处理\(c_i\)为\(a_i\)从小到大的数组，于是设\(f[i][j]\)表示处理到\(b_i\),这里令\(b_i=c_j\)的最小值，于是我们有

\[f[i][j]=\min_{k=1}^{j}(f[i-1][k])+|a_j-a_i|\]

根据策略集合，显然这里可以维护前缀小，于是可以优化到\(O(n^2)\)。

参考代码

#include <functional> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define il inline #define ri register #define intmax 0x7fffffff using namespace std; int A[2001],B[2001], dp[2001][2001],opt[2001]; il void read(int&); template<class free> il free Abs(free); template<class free> il free Min(free,free); int main(){ int n,i,j;read(n); for(i=1;i<=n;++i)read(A[i]),B[i]=A[i]; sort(B+1,B+n+1); for(i=1;i<=n;++i){ for(j=1;j<=n;++j) dp[i][j]=Abs(A[i]-B[j])+opt[j]; opt[1]=dp[i][1]; for(j=2;j<=n;++j)opt[j]=Min(opt[j-1],dp[i][j]); }int ans(intmax); for(i=1;i<=n;++i)ans=Min(ans,dp[n][i]); sort(B+1,B+n+1,greater<int>()); for(i=1;i<=n;++i){ for(j=1;j<=n;++j) dp[i][j]=Abs(A[i]-B[j])+opt[j]; opt[1]=dp[i][1]; for(j=2;j<=n;++j)opt[j]=Min(opt[j-1],dp[i][j]); }for(i=1;i<=n;++i)ans=Min(ans,dp[n][i]); printf("%d",ans); return 0; } template<class free> il free Min(free a,free b){ return a<b?a:b; } template<class free> il free Abs(free x){ return x<0?-x:x; } il void read(int &x){ x&=0;ri char c;while(c=getchar(),c<'0'||c>'9'); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); }

法三：

注意到绝对值解的移动性，故可以维护一个大根堆，如果加进去的数比大于等于堆顶，不管，如果小的话，就把这个数两次加进堆，ans累加堆顶-该数，再弹掉堆顶。

证明先放一放。

参考代码：

#include <iostream> #include <cstdio> #include <queue> #include <vector> #include <functional> #define il inline #define ri register using namespace std; priority_queue<int,vector<int>,less<int> >s; priority_queue<int,vector<int>,greater<int> >b; il void read(int&); int main(){ int n,i,a;read(n); int ans1(0),ans2(0); read(a),s.push(a),b.push(a); for(i=2;i<=n;++i){ read(a),s.push(a),b.push(a); if(a<s.top())ans1+=s.top()-a,s.pop(),s.push(a); if(a>b.top())ans2+=a-b.top(),b.pop(),b.push(a); }printf("%d",ans1>ans2?ans2:ans1); return 0; } il void read(int &x){ x&=0;ri char c;while(c=getchar(),c<'0'||c>'9'); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); }