P2893 [USACO08FEB] Making the Grade G(dp＆优先队列)

P2893 [USACO08FEB] Making the Grade G(dp&优先队列)

一个结论就是：修改后的值一定在 原序列出现过，这样是最优的。

将$a_i$ 离散化递增排序得到$b$

以递增为例子，然后就很显然令$dp(i,j)=min(dp(i,j),dp(i-1,k)+abs(a_i-b_j)),k\in [1,j]$

这里$min(dp(i-1,,k))$ 可以前缀和优化。

这样复杂度：$O(n^2)$

递减同理。

#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
int n,m,minf[2009][2009],f[2009][2009],a[2009],b[2009],t[2009],ans;
void ini()
{
    
  for (int i=0;i<=n;i++)
  for (int j=0;j<=m;j++)
  minf[i][j]=f[i][j]=0;
}
void dp()
{
    
 for (int i=1;i<=n;i++)
  for (int j=1;j<=m;j++)
  {
    
    f[i][j]=minf[i-1][j]+abs(a[i]-b[j]);
    if (j!=1) minf[i][j]=min(minf[i][j-1],f[i][j]);
    else minf[i][j]=f[i][j];
  }
}
int main()
{
    
  scanf("%d",&n);
  for (int i=1;i<=n;i++) 
  {
    
    scanf("%d",&a[i]);
    t[i]=a[i];
  }
  sort(t+1,t+1+n);
  int now=-1;
  for (int i=1;i<=n;i++) if (now!=t[i]) b[++m]=t[i],now=t[i];
  ini(); dp(); ans=minf[n][m]; 
  for (int i=1;i<=m/2;i++) swap(b[i],b[m-i+1]);
  ini(); dp(); ans=min(ans,minf[n][m]);
  printf("%d\n",ans);
  return 0;
}

---

更优的做法是用大根堆，每次丢$a_i$进堆，若比堆顶小，则把堆顶改成$a_i$。

花费$(x-y)$的费用，尽可能让$(y^{\prime })$最小，所以最优的情况就是$top=a_i$，也就是说尽可能让前面的最大值最小，保证后面空间更大。

时间复杂度：$O(nlogn)$

// Problem: P2893 [USACO08FEB] Making the Grade G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2893
// Memory Limit: 125 MB
// Time Limit: 3000 ms
// Date: 2022-06-30 22:45:26
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=2e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int hashmod[4] = {
    402653189,805306457,1610612741,998244353};
#define mst(a,b) memset(a,b,sizeof a)
#define db double
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define x first
#define y second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr) 
void Print(int *a,int n){
    
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
template <typename T>		//x=max(x,y) x=min(x,y)
void cmx(T &x,T y){
    
	if(x<y) x=y;
}
template <typename T>
void cmn(T &x,T y){
    
	if(x>y) x=y;
}
int n;
ll ans=0;
int a[N];
int main(){
    
	scanf("%d",&n);
	rep(i,1,n) scanf("%d",&a[i]);
	priority_queue<int>q;
	rep(i,1,n){
    
		int x = a[i];
		q.push(x);
		//printf("%d %d\n",x,q.top());
		if(x<q.top()){
    
			ans+=q.top()-x;
			q.pop();
			q.push(x);
		}
	}
	ll s =0;
	priority_queue<int,vector<int>,greater<int> >q1;
	rep(i,1,n){
    
		int x = a[i];
		q1.push(x);
		if(x>q1.top()){
    
			s+=x-q1.top();
			q1.pop();
			q1.push(x);
		}		
	}
	//printf("%lld %lld\n",ans,s);
	printf("%lld\n",min(ans,s));
	return 0;
}