Making the Grade

妖狐艹你老母 2022-01-08 00:25 188阅读 0赞

[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(); }

于是我们可以得到结论，递推随着状态优化，又可以转移时优化，但贪心显然排除了太多无用的状态，故是最好的优化方式。

转载于:https://www.cnblogs.com/a1b3c7d9/p/10902057.html

[Making the Grade]: http://poj.org/problem?id=3666