给定长度为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 
    
     #include 
     
      #include 
      
       #define il inline#define ri register#define intmax 0x7fffffffusing namespace std;int A[2001],dp[2001],sl[2001],    sr[2001];il void read(int&);template
       
        il free Abs(free);template
        
         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
         
          A[i])continue; sl[j]=sr[j]=0,l=intmax; for(k=j+1;k
          
           il free Min(free a,free b){ return a
           
            
             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 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define il inline#define ri register#define intmax 0x7fffffffusing namespace std;int A[2001],B[2001],    dp[2001][2001],opt[2001];il void read(int&);template
         
          il free Abs(free);template
          
           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
           
            ()); 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
            
             il free Min(free a,free b){ return a
             
              
               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 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define il inline#define ri registerusing namespace std;priority_queue
         
          
           ,less
           
             >s;priority_queue
            
             
              ,greater
              
                >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
               
                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();}
               
              
             
            
           
          
         
        
       
      
     
    

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