题解 P2893 【[USACO08FEB]修路Making the Grade】

· · 题解

萌新冒泡

这道题是一道较难的dp综合运用题

在手玩几组数据后 我们会发现一个数要么不改 要么改成原序列中某个数的值

（以下我们只讨论不下降序列）

比如100 250 130 如果要修改250 那肯定修改成130是最优的 而不是110 120等等

那我们或许可以尝试枚举当前数修改成的值？但由于 Ai ≤ 1,000,000,000，我们最好先离散化再来

那设f[i][j]表示第i个数修改成j(j是离散后的值)所需要的最小花费

则 f[i][j]=min{f[i-1][k]+abs(a[i]-b[j]) } (1<=k<=j b是排过序的数组)

然后这样好像是n^3的 考虑优化 我这里采用了类似单调队列的方式 边枚举j边更新

//n^2
#include<bits/stdc++.h>
const int N=2005;
const int INF=0x3f3f3f3f;
using namespace std;
int n,m,a[N],b[N],dp[N][N],ans,q[N],tail;
int minx=INF;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)   cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
    {
        tail=0;
        for(int j=1;j<=n;j++)
        {
            while(tail&&dp[i-1][j]<dp[i-1][q[tail]])    tail--;
            q[++tail]=j;
            dp[i][j]=dp[i-1][q[1]]+abs(a[i]-b[j]); 
        }
    }
    ans=INF;
    for(int i=1;i<=n;i++)   ans=min(ans,dp[n][i]);
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        tail=0;
        for(int j=n;j>=1;j--)    //倒序枚举保证k∈[j,n]
        {
            while(tail&&dp[i-1][j]<dp[i-1][q[tail]])    tail--;
            q[++tail]=j;    
            dp[i][j]=dp[i-1][q[1]]+abs(a[i]-b[j]);
        }
    }   
    for(int i=1;i<=n;i++)   ans=min(ans,dp[n][i]);
    cout<<ans<<endl;
    return 0;
}