Making the Grade

· · 题解

×这是一种 n^3的做法

状态定义

### 状态转移 $f[i]=min{f[j]+cost(j+1,i-1)};(0<=j<i)(ai<=aj) ### 思路 由引理可知$b[i]$由$a[i]$中的一段段数构成。 把$b$的区间$[j+1,k]$中的数变为$a[j]$，后面的$[k+1，i-1]$中的数变为$a[i]

的最小花费

不需要考虑其中b[k]中的一部分数会变成a[k]，因为该情况在j=k时已经被考虑到。

（以上垃圾缩写《算法竞赛进阶指南》）

但……f[n]并不是答案，因为最后的数b[n]可能不等于a[n]，所以要对答案进行一下微妙的处理，其实就是把b[i+1]一直到b[n]全都赋成a[i]就好，然后统计下答案。


#include<bits/stdc++.h>
using namespace std;
long long a[2001];
long long f[2001];
    long long ans=LLONG_MAX;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        f[i]=LLONG_MAX;
    }
    f[0]=0;
    for(int i=1;i<=n;i++)
    {   

        for(int j=0;j<=i-1;j++)
        {   
            if(a[i]<a[j])
                continue;   
            long long cost=0;
            long long res=LLONG_MAX;
            for(int k=j+1;k<=i-1;k++)cost+=abs(a[k]-a[i]);

            res=min(res,cost);
            for(int k=j+1;k<=i-1;k++){
                cost=cost-abs(a[k]-a[i])+abs(a[j]-a[k]);
                res=min(res,cost);
            }
            f[i]=min(f[i],f[j]+res);
        }
    }

    for(int i=1;i<=n;i++)
    {
        long long res=f[i];
        for(int j=i+1;j<=n;j++)
        {
            res+=abs(a[i]-a[j]);
        }
        ans=min(ans,res);
    }
    printf("%lld\n",ans);

    return 0;
}

其实我写这个的原因是在网上找不到这种写法的代码

此非正解（仅供娱乐）90‘